認(rèn)知無線Mesh網(wǎng)絡(luò)自適應(yīng)多路徑算法*

章國安,2,丁晨莉,包志華

(1.南通大學(xué) 電子信息學(xué)院，江蘇 南通 226019;2.東南大學(xué) 移動通信國家重點(diǎn)實(shí)驗(yàn)室，南京 210096)

1 引 言

認(rèn)知無線Mesh網(wǎng)絡(luò)(Cognitive Wireless Mesh Networks, CogWMN)是一種利用 認(rèn)知無線電(Cognitive Radio，CR)技術(shù)的無線Mesh網(wǎng)絡(luò)，配有CR模塊的CMesh(Cognitive Mesh)節(jié)點(diǎn)能夠感知主系統(tǒng)的空閑頻譜、動態(tài)接入空閑頻譜。CogWMN是一種結(jié)合CR與WMN新型的網(wǎng)絡(luò)形式[1-2]。

在認(rèn)知無線Mesh網(wǎng)絡(luò)環(huán)境下，即使尋找到最優(yōu)的一條路徑傳輸業(yè)務(wù)數(shù)據(jù)流，也仍然會因避讓首要用戶使用授權(quán)信道而暫時中斷業(yè)務(wù)流的傳輸，導(dǎo)致數(shù)據(jù)流延時。利用多路徑傳輸，即使其中一條路徑被破壞，其它路徑節(jié)點(diǎn)也可以繼續(xù)傳輸數(shù)據(jù)包，減少數(shù)據(jù)包延時，保障服務(wù)質(zhì)量。文獻(xiàn)[3]指出相比無認(rèn)知環(huán)境的網(wǎng)絡(luò)，在認(rèn)知環(huán)境下，網(wǎng)絡(luò)內(nèi)多路徑傳輸?shù)难訒r、平均丟包率、平均隊(duì)列時間均有所下降。

近年來，強(qiáng)化學(xué)習(xí)被應(yīng)用在無線網(wǎng)絡(luò)內(nèi)。多agent系統(tǒng)可用來很自然地模擬與抽象現(xiàn)實(shí)中分布、動態(tài)、開放、復(fù)雜的問題[4]，在認(rèn)知環(huán)境下，多agent強(qiáng)化學(xué)習(xí)能夠幫助節(jié)點(diǎn)感知更多的頻譜或者進(jìn)行有效的功率控制[5-6]。為了減小變化的頻譜空穴給路徑傳輸帶來的負(fù)面影響，使網(wǎng)絡(luò)節(jié)點(diǎn)能夠自適應(yīng)選擇較優(yōu)路徑傳輸數(shù)據(jù)，本文提出了基于多agent強(qiáng)化學(xué)習(xí)的多路徑自適應(yīng)路由(Multi-Path Q Reinforcement Learning Algorithm，MPQRLA)，能夠適應(yīng)認(rèn)知無線Mesh網(wǎng)絡(luò)動態(tài)變化的環(huán)境。

2 基于多agent的自適應(yīng)多路徑算法

2.1 多agent的強(qiáng)化學(xué)習(xí)模型

如圖1所示，配有認(rèn)知無線電模塊的CMesh節(jié)點(diǎn)根據(jù)認(rèn)知環(huán)境感知信道和估計(jì)其周圍首要用戶的功率、距離等，進(jìn)入初始狀態(tài)，經(jīng)過一系列中間狀態(tài)及其行動選擇，達(dá)到較理想的狀態(tài)，即傳輸業(yè)務(wù)流狀態(tài)。CMesh節(jié)點(diǎn)通過求解策略π、感知突發(fā)環(huán)境的變化以及回報(bào)結(jié)果選擇路徑，估計(jì)下一個傳輸狀態(tài)。然后通過動作選擇器，向下一跳鄰節(jié)點(diǎn)發(fā)送數(shù)據(jù)包、計(jì)算鏈路擁塞指數(shù)等參數(shù)，判斷滿意度是否滿足目標(biāo)閾值，決定是否繼續(xù)該路徑的使用。當(dāng)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)業(yè)務(wù)傳輸時，計(jì)算滿意度，對放棄該路徑、改變路徑或者切換信道等作出抉擇。

圖1 多agent強(qiáng)化學(xué)習(xí)模型

2.2 基于Markov的多agent強(qiáng)化學(xué)習(xí)模型

定義七元組{N,S,A,T,R,D,θ}為基于Markov模型的多agent的強(qiáng)化學(xué)習(xí)模型[7]，其中N表示n個agent集合，這些agent在網(wǎng)絡(luò)內(nèi)對應(yīng)網(wǎng)絡(luò)節(jié)點(diǎn)，包含CMesh節(jié)點(diǎn)和接入節(jié)點(diǎn)AP；S=(S1,S2,S3,…,Sn)表示n個agent離散狀態(tài)有限集合；A=(A1,A2,A3,…,An) 表示n個agent行動集合；T：S×A×S→[0,1]表示狀態(tài)轉(zhuǎn)移；R=(R1,R2,R3,…,Rn)表示n個agent各自的回報(bào)函數(shù)；D表示學(xué)習(xí)滿意度；θ表示目標(biāo)閾值，如果滿足D>θ，則在p概率下遷移到符合要求的狀態(tài)。

2.3 Q值函數(shù)的描述

Q值函數(shù)最優(yōu)值的計(jì)算：

(1)

路由f上Q總值計(jì)算：

(2)

路由f上Q總值更新值的計(jì)算：

Qf(s,a)=(1-α)Qf(s,a)+

α[R+γminQf(s′,a′)]

(3)

當(dāng)頻譜空穴改變，需要更換路徑或者更換信道時，需要預(yù)估新的狀態(tài)s′和動作a′。策略π是從Q總值中找到的，該策略旨在f所找到路由中有一條Q值最優(yōu)的路徑，定義為

π=minQf(s,a)

(4)

回報(bào)函數(shù)R定義為公式(5)，表示預(yù)算數(shù)據(jù)流經(jīng)過節(jié)點(diǎn)i到j(luò)的丟包、延時等，ploss,j以及pdelay,j為丟包和延時的懲罰因子，0

(5)

為了將S狀態(tài)更明確，我們將S擴(kuò)展得到：

St,i={It,i,Pt,i,Ct,i,ch}

(6)

式中，It,i表示SINR是否大于信干比的門限，取值為0或1；Pt,i表示功率水平，確保在限制的功率內(nèi)，不會對周圍首要用戶造成干擾；Ct,i,ch表示信道ch的信道擁塞指數(shù)，指示是否接受鄰節(jié)點(diǎn)的連接要求。

預(yù)算滿意度D的計(jì)算公式：

(7)

式中，BWf代表要求的網(wǎng)絡(luò)帶寬，bwf代表實(shí)際傳輸?shù)膸?。滿意度不滿足閾值時，將可能放棄該路徑。

實(shí)際滿意度D的計(jì)算公式如下：

(8)

式中，THRf代表要求的吞吐量，thrf代表實(shí)際傳輸?shù)耐掏铝?。滿意度小于其閾值時，將更換路徑或信道。

2.4 多路徑的調(diào)度策略

多agent強(qiáng)化學(xué)習(xí)的目標(biāo)是使節(jié)點(diǎn)能計(jì)算出最佳路徑，源節(jié)點(diǎn)計(jì)算出最佳路徑后，只有一條路徑傳輸數(shù)據(jù)。為了能實(shí)現(xiàn)多路徑的傳輸，這里設(shè)定， 源節(jié)點(diǎn)經(jīng)過T時間，依據(jù)環(huán)境變化等因素，計(jì)算第二條最佳路徑，兩條路徑同時傳輸，達(dá)到負(fù)載平衡的目的。假若其中任意一條路徑因滿意度下降到閾值后或因其它因素，放棄該路徑，仍然有一條路徑繼續(xù)傳輸數(shù)據(jù)，這樣延時波動不會較大。源節(jié)點(diǎn)經(jīng)過T時間，計(jì)算第二條最佳路徑，此路徑為除正使用路徑外的最佳路徑，恢復(fù)兩條路徑同時傳輸數(shù)據(jù)。多路徑的調(diào)度策略可使源節(jié)點(diǎn)到目的節(jié)點(diǎn)總有一條路徑在傳輸，并且可能是暫時的最優(yōu)路徑在傳輸，保證服務(wù)質(zhì)量。多路徑策略框圖如圖2所示。

圖2 多路徑策略流程圖

3 自適應(yīng)路由算法描述

3.1 Q值函數(shù)路由表

Q值函數(shù)路由表是一張二維表格，表示節(jié)點(diǎn)i到節(jié)點(diǎn)j的單跳最優(yōu)Q值，通過Q值路由表可計(jì)算出路由f上Q總值以及路由f上Q總值的更新值。

如圖3(a)所示，網(wǎng)絡(luò)內(nèi)5個CMesh節(jié)點(diǎn)，其中節(jié)點(diǎn)4～5有兩個可用信道1和5，根據(jù)公式(1)和(2)分別計(jì)算單跳節(jié)點(diǎn)Q值和總Q值，由于Q值路由表記錄的第4行第5列格子中是5號信道的Q值2，因此節(jié)點(diǎn)4～5的5號信道Q值最小。根據(jù)公式(4)的策略π，得到路徑1-3-4-5為最佳路徑。

(a)簡單網(wǎng)絡(luò)模型

(b)Q值路由表

當(dāng)該路徑中的節(jié)點(diǎn)3～4可用信道變化時，如圖4(a)所示。設(shè)定折扣因子和學(xué)習(xí)速率為0.2和0.5，由公式(3)和公式(5)，可得更新后的最佳路徑為1-2-4-5，如圖4(b)所示。

(a)變化后的網(wǎng)絡(luò)模型

(b)更新后的Q值路由表

3.2 自適應(yīng)多路徑算法描述

多agent強(qiáng)化學(xué)習(xí)的目標(biāo)是使節(jié)點(diǎn)能計(jì)算出最佳路徑，當(dāng)網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)感知空閑的可用信道后，進(jìn)入最佳路徑的選擇階段，其算法如下：

(1)初始化節(jié)點(diǎn)S和A；

(2)通過公用控制信道，當(dāng)相鄰節(jié)點(diǎn)可用信道交集非空時，計(jì)算所有路徑f，以及ξ(f)和N(i)；

(3)根據(jù)公式(1)和(2)，分別計(jì)算單跳節(jié)點(diǎn)最優(yōu)Q值，得到Q值路由表，計(jì)算路徑總Q值；

(4)根據(jù)公式(4)，獲得最優(yōu)路徑傳輸業(yè)務(wù)，轉(zhuǎn)入多路徑的調(diào)度策略；

(5)當(dāng)頻譜空穴變化后需要變更信道時，觀察回報(bào)值R，更新單跳Q值，轉(zhuǎn)入步驟6；當(dāng)放棄路徑或者重新選擇路徑時，轉(zhuǎn)入步驟1；

(6)根據(jù)公式(7)，預(yù)算變更信道的滿意度D，選擇D>θ的新狀態(tài)s′和動作a′；

(7)存儲Q值和更新Q值總值，根據(jù)策略π，更新最佳路徑；

(8)根據(jù)公式(8)，當(dāng)正在使用的路徑滿意度下降到θ以下后，放棄該路徑并更改路徑，轉(zhuǎn)入步驟5。

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

本文使用Matlab語言仿真基于多agent強(qiáng)化學(xué)習(xí)多路徑CogWMN自適應(yīng)路由算法性能。網(wǎng)絡(luò)內(nèi)有40個CMesh節(jié)點(diǎn)，隨機(jī)分布在500 m×500 m的范圍內(nèi)，仿真時間為1 000 s。假設(shè)首要用戶工作在712～757 MHz的頻段內(nèi)，每信道帶寬為5 MHz，共有10個信道。丟包和延時的懲罰因子都為0.5，折扣因子為0.2，學(xué)習(xí)率為0.85，滿意度閾值為0.8。在CogWMN內(nèi)，更換路徑的主要原因之一是因可用信道變化使傳輸路徑暫時不可用，導(dǎo)致CMesh節(jié)點(diǎn)退避延時。將本文提出的自適應(yīng)多路徑算法與隨機(jī)(Random)路由與信道分配算法和Dijkstra最短路徑(Shortest Path，SP)算法分別應(yīng)用于AODV路由協(xié)議，并比較三者之間的滿意度、平均端到端延時、丟包率以及分組成功投遞率。

圖5所示為滿意度對比，由于預(yù)設(shè)的目標(biāo)閾值是0.8，所以MPQRLA的滿意度一直都在0.8以上，而對比的兩種算法滿意度不如MPQRLA。

圖5 滿意度

圖6所示是平均端到端延時對比，從圖中看出MPQRLA的延時比SP和random小，這是因?yàn)橛?jì)算Q值函數(shù)時考慮了數(shù)據(jù)包在鄰節(jié)點(diǎn)間來回所需的時間。

圖6 平均端到端延時

圖7所示為丟包率的對比，由于MPQRLA采用了多路徑的調(diào)度策略，任意一條路徑因滿意度下降到閾值后或因其它因素，放棄該路徑，仍然有一條路徑繼續(xù)傳輸數(shù)據(jù)，這樣丟包情況有所控制。

圖7 丟包率

圖8所示是網(wǎng)絡(luò)節(jié)點(diǎn)的分組成功投遞率，從圖中看出，MPQRLA的成功率較高。

圖8 分組成功投遞率

5 結(jié)束語

在認(rèn)知無線Mesh網(wǎng)絡(luò)環(huán)境下，即使尋找到最優(yōu)單路徑傳輸數(shù)據(jù)流，也仍然會因避讓首要用戶使用主信道而暫時中斷數(shù)據(jù)流的傳輸。本文提出的多agent自適應(yīng)多路徑算法，節(jié)點(diǎn)感知環(huán)境后進(jìn)入初始狀態(tài)，通過Q-學(xué)習(xí)算法更新Q值路由表學(xué)習(xí)最佳路徑，并結(jié)合多路徑調(diào)度策略實(shí)現(xiàn)多路徑傳輸。當(dāng)頻譜空穴變化后需要更換路徑時，通過觀察回報(bào)值、計(jì)算滿意度等，自適應(yīng)學(xué)習(xí)恢復(fù)多路徑傳輸，保障服務(wù)質(zhì)量。仿真結(jié)果表明，該算法能夠提高網(wǎng)絡(luò)性能，在滿意度、平均端到端延時、丟包率以及分組成功投遞率上都有較好的表現(xiàn)。

參考文獻(xiàn)：

[1] 丁晨莉,章國安,包志華.基于模糊推理的認(rèn)知無線Mesh網(wǎng)絡(luò)路由算法[J].電訊技術(shù),2009,49(11):35-39.

DING Chen-li,ZHANG Guo-an,BAO Zhi-hua.A CogWMN Routing Algorithm Based on Fuzzy Petri Net [J].Telecommunication Engineering,2009,49(11):35-39.(in Chinese)

[2] Chen T, Zhang H, Matinmikko M, et al. CogMesh: Cognitive Wireless Mesh Networks[C]// Proceedings of IEEE Global Telecommunications Conference. New Orleans, LA:IEEE,2008:1-6.

[3] Javadi F, Jamalipour A. Multi-Path Routing for a Cognitive Wireless Mesh Network[C]//Proceedings of International Conference on Radio and Wireless Symposium. New Orleans, LA:IEEE,2009:232-235.

[4] 陳宗海,楊志華,王海波,等.從知識的表達(dá)和運(yùn)用綜述強(qiáng)化學(xué)習(xí)研究[J].控制與決策,2008,23(9):961-975.

CHEN Zong-hai, YANG Zhi-hua, WANG Hai-bo,et al. Overview of reinforcement learning from knowledge expression and handling[J]. Control and Decision, 2008, 23(9):961-975.(in Chinese)

[5] Xia B, Wahab M H, Yang Y, et al. Reinforcement Learning Based Spectrum-aware Routing in Multi-hop Cognitive Radio Networks[C]// Proceedings of the 4th International Conference on Cognitive Radio Oriented Wireless Networks and Communications. Hannover：IEEE, 2009:1-5.

[6] Serrano A G, Giupponi L. Aggregated Interference Control for Cognitive Radio Networks Based on Multi-agent Learning[C]//Proceedings of the 4th International Conference on Cognitive Radio Oriented Wireless Networks and Communications. Hannover:IEEE,2009:1-6.

[7] 劉菲,曾廣周.基于強(qiáng)化學(xué)習(xí)的多移動Agent學(xué)習(xí)算法[J].計(jì)算機(jī)工程與應(yīng)用, 2006, 42(5):50-53.

LIU Fei, ZENG Guang-zhou.Multi Mobile Agent Learning Algorithm Based on Reinforcement Learning [J].Computer Engineering and Applications,2006,42(5):50-53.(in Chinese)

[8] Ziane S, Mellouk A. A QoS Adaptive Multi-path Reinforcement Learning Routing Algorithm for MANET[C]//Proceedings of ACS International Conference on Computer Systems and Applications.Amman,Jordan:IEEE/ACS,2007:659-664.

[9] TaoT, Tagashira S, Fujita S. LQ-Routing Protocol for Mobile Ad-Hoc Networks[C]//Proceedings of the 4th ACIS International Conference on Computer and Information Science. Jeju Island, South Korea:IEEE,2005:441-446.