基于部分可觀察馬氏決策過(guò)程的頻譜接入方法

侯國(guó)濤 韓 慧 胡 俊

(1．電子信息系統(tǒng)復(fù)雜電磁環(huán)境效應(yīng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，河南 洛陽(yáng) 471003；2．中國(guó)電波傳播研究所，山東 青島 266107)

引 言

Joseph Mitola III在1999年提出認(rèn)知無(wú)線電概念[1-3]，期望通信更加智能化、更加靈活化，頻譜資源得到更加合理利用[4-6].以下幾方面更促進(jìn)了認(rèn)知無(wú)線電的研究和應(yīng)用.

1) 頻譜緊張是認(rèn)知無(wú)線電產(chǎn)生的主要因素之一.現(xiàn)在的頻譜分配政策是在大面積范圍內(nèi)將頻率固定分配給一種用途.這種靜態(tài)的頻率分配方式導(dǎo)致寶貴的頻譜資源未被充分利用.

2) 各種電子技術(shù)更新使得認(rèn)知無(wú)線電成為可能.例如，認(rèn)知無(wú)線電需要寬帶射頻前端、高靈敏度檢測(cè)門限、靈活的頻率捷變能力等等.軟件無(wú)線電或叫做軟件定義無(wú)線電思想為實(shí)現(xiàn)認(rèn)知無(wú)線電奠定了基礎(chǔ).智能天線技術(shù)為認(rèn)知無(wú)線電避免對(duì)其他用戶造成干擾創(chuàng)造了條件.特別是人工智能、機(jī)器學(xué)習(xí)等技術(shù)更加速了認(rèn)知無(wú)線電實(shí)現(xiàn)的步伐.

3) 相關(guān)政策和制度為認(rèn)知無(wú)線電應(yīng)用掃清了障礙[7].雖然大部分已分配的頻譜利用率很低，但是現(xiàn)有的頻譜使用制度不允許未授權(quán)無(wú)線電設(shè)備使用那些未充分利用的授權(quán)頻譜.世界各國(guó)的頻譜管理組織和機(jī)構(gòu)認(rèn)識(shí)到低利用率的授權(quán)頻段的再利用潛力后，都在調(diào)整相關(guān)的政策，使得這些未充分利用的授權(quán)頻段可以被合法地分配和利用.

1 POMDP

部分可觀察馬爾科夫決策過(guò)程POMDP由以下六重組表示[8]

Ξ=(S,A,Z,R,T,O),

(1)

式中各元的意義如下：

1)S是外部環(huán)境的狀態(tài)集，狀態(tài)不可被決策主體或機(jī)器人(Agent)直接獲得；

2)A是Agent可用的策略集，策略的執(zhí)行將影響系統(tǒng)的狀態(tài)和觀察值；

3)Z是Agent對(duì)環(huán)境的觀察集；

O:A×S→Π(Z) ,

(2)

式中Π(Z)是觀察集Z上的全體概率分布的集合.

4) 報(bào)酬函數(shù)：

r:S×A→R,

(3)

式中r(s,a)表示系統(tǒng)處于狀態(tài)s，執(zhí)行決策a∈A后，獲得的即時(shí)報(bào)酬.

5) 狀態(tài)轉(zhuǎn)移函數(shù)：

T：S×A→Π(S) ,

(4)

式中Π(S)是狀態(tài)集S上的全體概率分布的集合.當(dāng)系統(tǒng)在決策時(shí)刻點(diǎn)t處于狀態(tài)s，采取決策a∈A(s)后，系統(tǒng)在下一決策時(shí)刻點(diǎn)t+1時(shí)處于狀態(tài)s′的概率為

τ(s,a,s′)=P(St+1=s′|St=s,At=a),

(5)

它與決策時(shí)刻t無(wú)關(guān).

6) 觀察函數(shù)：

o(a,s,z)=P(Ot=z|St=s,At-1=a) ，

(6)

表示在t-1時(shí)刻執(zhí)行動(dòng)作a后，系統(tǒng)狀態(tài)在t時(shí)轉(zhuǎn)移到s，觀察到z的概率.

圖1描述了在POMDP中Agent與外部環(huán)境信息交互.在決策時(shí)刻t時(shí)，系統(tǒng)所處的狀態(tài)為s，Agent不能準(zhǔn)確知道系統(tǒng)所處的狀態(tài).Agent只能通過(guò)系統(tǒng)狀態(tài)的估計(jì)值b按照某策略執(zhí)行動(dòng)作a，獲得回報(bào)r(s,a).在t+1時(shí)外部環(huán)境狀態(tài)轉(zhuǎn)移到狀態(tài)s′，同時(shí)得到系統(tǒng)狀態(tài)的觀察值z(mì).Agent根據(jù)觀察值z(mì)、前一決策時(shí)刻t的動(dòng)作a和狀態(tài)估計(jì)值b，估計(jì)出當(dāng)前時(shí)刻t+1時(shí)的狀態(tài)b′.如此重復(fù)上述步驟，直至決策長(zhǎng)度結(jié)束.

圖1 POMDP模型

在基于POMDP的機(jī)會(huì)式頻譜接入方法中，次用戶作為決策主體，就是要和外界電磁環(huán)境(頻譜空穴)進(jìn)行交互的Agent.

2 信道模型

某主用戶網(wǎng)絡(luò)擁有N個(gè)信道的使用權(quán)，每個(gè)信道的寬度為Bn(n=1,…,N).假設(shè)這N個(gè)信道被主用戶占用情況可以用狀態(tài)數(shù)為2N的齊次馬爾科夫鏈模型.在時(shí)間t，信道n的占用情況可以表示為

Sn(t)∈(0,1),

(7)

式中：0表示被主用戶占用，次用戶不能使用； 1表示信道空閑，可以被次用戶利用.

整個(gè)頻譜的占用狀態(tài)可以表示為

S(t)[SN(t),…，S1(t)].

(8)

轉(zhuǎn)移概率表示為

Ps,s′P(S(t)=s′|S(t-1)=s),

(9)

表示頻譜占用狀態(tài)在t時(shí)刻由狀態(tài)s∈S轉(zhuǎn)移到s′∈S的概率.狀態(tài)轉(zhuǎn)移概率僅僅由主用戶通信量的動(dòng)態(tài)特性決定.

3 頻譜接入模型

部分可觀察馬爾科夫決策過(guò)程的兩個(gè)特點(diǎn)：Agent的行動(dòng)不確定性和觀察不確定性.而次用戶選擇某信道接入后，信道狀態(tài)的不確定性符合POMDP的行動(dòng)不確定性；次用戶不能準(zhǔn)確知道信道占用狀態(tài)符合POMDP的觀察不確定性.因?yàn)榇斡脩暨x擇信道接入的決策階段長(zhǎng)度是無(wú)限的，故模型化為無(wú)限階POMDP.在1節(jié)中介紹的部分可觀察馬爾科夫決策過(guò)程的六重組，在這里一一定義.

狀態(tài)空間：系統(tǒng)的狀態(tài)是信道被主用戶網(wǎng)絡(luò)占用狀態(tài)，用式(8)表示.狀態(tài)空間集為S={0,1}N.

行動(dòng)空間：在每個(gè)時(shí)隙t的開(kāi)始，從N個(gè)信道中選擇某個(gè)信道n進(jìn)行接入.行動(dòng)表示為an(t)，表示在時(shí)隙t接入信道n.圖2表示次用戶系統(tǒng)的每個(gè)時(shí)隙結(jié)構(gòu)圖.在每個(gè)時(shí)隙的開(kāi)始次用戶得到有關(guān)系統(tǒng)狀態(tài)的觀察，在剩余的時(shí)間里次用戶占用信道n.

圖2 時(shí)隙結(jié)構(gòu)

轉(zhuǎn)移概率：系統(tǒng)的狀態(tài)轉(zhuǎn)移概率由Ps,s′表示，由主用戶通信量的動(dòng)態(tài)特性決定，可表示為

τ(s,a,s′)=Ps,s′.

(10)

轉(zhuǎn)移概率僅僅由主用戶的通信情況決定，次用戶的動(dòng)作a與狀態(tài)轉(zhuǎn)移概率無(wú)關(guān).信道轉(zhuǎn)移概率統(tǒng)計(jì)特性在有限時(shí)間內(nèi)可以被次用戶學(xué)習(xí)得知[9].本文假設(shè)次用戶已經(jīng)得知信道的轉(zhuǎn)移概率.

觀察空間：觀察空間Z={0,1}.觀察1表示信道未被占用；觀察0表示信道被占用，即：

(11)

回報(bào)：回報(bào)是與接入信道的帶寬成正比的.

(12)

式中R表示回報(bào)，通常為了保護(hù)主用戶權(quán)益，在Sn(t)=0時(shí)，懲罰比回報(bào)大很多.

觀察函數(shù)：

o(a,s′,z)=P(O(t)=z|S(t)=s′,

A(t-1)=an,

(13)

表示的含義為：在t-1時(shí)刻，對(duì)信道n進(jìn)行接入后，在t時(shí)刻系統(tǒng)狀態(tài)轉(zhuǎn)移為s′時(shí)，并得到觀察為z的概率.

信念向量：次用戶不能準(zhǔn)確地確定系統(tǒng)所處的狀態(tài)，用信念向量表示對(duì)系統(tǒng)狀態(tài)的估計(jì).在開(kāi)始時(shí)刻，次用戶可以用系統(tǒng)的實(shí)際狀態(tài)作為模型的初始信念狀態(tài).整個(gè)觀察和決策歷史對(duì)信道占用情況提供的統(tǒng)計(jì)信息可以用信念向量表示

b(t){bs(t)}s∈S∈Π(S) ,

(14)

式中bs(t)表示系統(tǒng)狀態(tài)在t時(shí)隙時(shí)處在狀態(tài)s的概率，如b(000)=0.1表示系統(tǒng)處在狀態(tài)000的概率為0.1.

值函數(shù)：

(15)

式中ρ∈(0.1)稱為折扣因子，保證了式(15)具有收斂性.值函數(shù)的意義是，在無(wú)限決策長(zhǎng)度內(nèi)期望折扣總回報(bào).在本模型中用有限階段值函數(shù)去逼近無(wú)限階段值函數(shù).逼近的好壞用下式表示：

max(Vn+1-Vn)

(16)

式中,e是較小的數(shù)，按系統(tǒng)要求設(shè)置.當(dāng)滿足式(16)時(shí)，則Perseus算法[10-14]找到了滿足要求的解，程序結(jié)束.

策略：選擇最優(yōu)信道進(jìn)行探測(cè)，使得在無(wú)限執(zhí)行階段內(nèi)獲得的期望折扣總回報(bào)最大，即：

(17)

最優(yōu)策略為

π*=(d*,d*,…,d*).

(18)

4 頻譜接入仿真

4.1 模型參數(shù)設(shè)置

設(shè)信道個(gè)數(shù)N=3，狀態(tài)空間數(shù)量為2N=23=8，狀態(tài)空間集為：

S={000,001,010,011,100,101,110,111} .

(19)

用S0～S7表示，每個(gè)狀態(tài)從右到左分別表示信道1，信道2，信道3的狀態(tài).例如，狀態(tài)011表示信道1、信道2可以被次用戶利用，信道3不能被次用戶利用.

an(t)表示在時(shí)隙t內(nèi)接入信道n進(jìn)行數(shù)據(jù)傳輸，行動(dòng)空間集為

A={a1(t),a2(t),a3(t)} .

(20)

狀態(tài)轉(zhuǎn)移函數(shù)式(10)，式中a為動(dòng)作空間中的動(dòng)作，狀態(tài)轉(zhuǎn)移是與動(dòng)作a無(wú)關(guān)的.表1所示狀態(tài)函數(shù)轉(zhuǎn)移表，表中的行表示從一個(gè)狀態(tài)轉(zhuǎn)移到其他各狀態(tài)的概率.

表1 狀態(tài)轉(zhuǎn)移函數(shù)表

表2、表3分別表示z=1，z=0時(shí)的觀察函數(shù)表.例如，次用戶接入信道1(執(zhí)行動(dòng)作a1)后狀態(tài)轉(zhuǎn)移為S1，觀察到z=1的概率為0.85，觀察到z=0概率是0.15.

表2 z=1時(shí)觀察函數(shù)表

表3 z=0時(shí)觀察函數(shù)表

在仿真時(shí)，信念狀態(tài)集B是隨機(jī)生成的，要滿足信念狀態(tài)點(diǎn)各分量之和為1.信念狀態(tài)點(diǎn)的個(gè)數(shù)越多越能準(zhǔn)確刻畫值函數(shù)的微小變化，M為信念點(diǎn)個(gè)數(shù).接下來(lái)的4.2節(jié)中考察的那些點(diǎn)都是從隨機(jī)生成的信念點(diǎn)中抽取的具有代表性的點(diǎn).回報(bào)函數(shù)表將根據(jù)不同的信道帶寬設(shè)定，將根據(jù)不同情況進(jìn)行表述.

4.2 模型仿真

下面仿真次用戶選擇信道接入情況，信道帶寬Bn=1 MHz，ρ=0.95(折扣因子)，M=1 000(M表示仿真中信念狀態(tài)點(diǎn)集個(gè)數(shù)).表4挑選了具有代表性的8個(gè)信念點(diǎn)，b1中表示信道1空閑概率較高，類似的還有b2，b3，次用戶應(yīng)當(dāng)選擇信道空閑概率高的接入.b4中信道空閑概率都比較低，則需通過(guò)仿真查看次用戶選擇那個(gè)信道接入.b5，b6，b7,b8表示空閑信道不至1個(gè)時(shí)，次用戶選擇那個(gè)信道接入.

表4 8個(gè)代表性的信念點(diǎn)

信道帶寬Bn=1 MHz，即各信道帶寬都相同，回報(bào)r(s,a)函數(shù)表如表5.

表5 回報(bào)函數(shù)表

仿真結(jié)果如圖3～圖6所示.從圖3、圖4中看到，狀態(tài)點(diǎn)b1可以看到這時(shí)系統(tǒng)處在001的概率最大，所以在第5步運(yùn)行時(shí)，次用戶接入信道1.類似b1點(diǎn)還有b2、b3.b5信念點(diǎn)最能體現(xiàn)算法追求最大期望折扣總回報(bào)的特點(diǎn)，這時(shí)系統(tǒng)處在011狀態(tài)概率最大.通過(guò)幾步的學(xué)習(xí)，可以看到在第5步時(shí)選擇信道1接入.類似b5點(diǎn)還有b7點(diǎn).b4這個(gè)信念點(diǎn)是最難確定系統(tǒng)中那個(gè)信道空閑的狀態(tài)點(diǎn)，可以看到次用戶在信道2和信道3中不停轉(zhuǎn)換.從圖5、圖6中可以看到，經(jīng)過(guò)25步后，在b4點(diǎn)找到了最優(yōu)動(dòng)作：接入信道3. 信念點(diǎn)b6表明系統(tǒng)處在000狀態(tài)的概率很高，雖然經(jīng)過(guò)多步后，在此點(diǎn)的期望折扣總回報(bào)仍然很低.在實(shí)際應(yīng)用中，可設(shè)計(jì)一個(gè)動(dòng)作專門針對(duì)000狀態(tài)，比如動(dòng)作a4=等待，這樣期望折扣總回報(bào)函數(shù)值會(huì)得到改善.b8表明系統(tǒng)在111的概率最高，從圖5、圖6中可以看到，選擇的接入信道也在變換，但期望折扣總回報(bào)是相同的.

圖3 第3步運(yùn)行圖

圖4 第5步運(yùn)行圖

圖5 第25步運(yùn)行圖

圖6 第50步運(yùn)行圖

5 結(jié) 論

把次用戶選擇接入信道模型化為無(wú)限階部分可觀察馬爾科夫決策過(guò)程后，對(duì)其進(jìn)行了系統(tǒng)仿真.仿真表明，次用戶選擇使得期望折扣總回報(bào)達(dá)到最大的信道進(jìn)行接入.

[1] MITOLA J. Cognitive Radio: An Integrated Agent Architecture for Software Defined Radio[D]. Stockholm: the Royal Institute of Technology,2000.

[2] MITOLA J, MAGUIRE, GERALD Q, et al, Cognitive Radio: Making software radios more personal[J]. IEEE Pers.Commun, 1999, 6(4): 13-18.

[3] Federal Communications Commission. Spectrum Policy Task Force, Rep[R]. Washington D C: FCC Document ET Docket no. 02-155, 2002.

[4] 黃 川, 鄭寶玉.一種新型認(rèn)知無(wú)線電信道狀態(tài)的預(yù)測(cè)算法[J]. 華僑大學(xué)學(xué)報(bào)(自然科學(xué)版),2010, 31(15): 521-525.

HUANG Chuan, ZHENG Baoyu. A novel channel state prediction algorithm of cognitive radio[J]. Quanzhou Fujian: Journal of Huaqiao University: Natural Science, 2010, 31(15): 521-525. (in Chinese)

[5] 舒鵬飛, 李 政, 譚學(xué)治, 等. 基于POMDP的認(rèn)知無(wú)線電動(dòng)態(tài)頻譜接入算法[J]. 北京: 科學(xué)技術(shù)與工程,2009, 9(12): 3288-3291.

SHU Pengfei, LI Zheng, TAN Xuezhi, et al. POMDP based dynamic spectrum access algorithm in cognitive radio[J]. Beijing: Science Technology and Engineering, 2009, 9(12): 3288-3291. (in Chinese)

[6] 李曉婭，張有光，吳華森.認(rèn)知無(wú)線電中基于POMDP 的機(jī)會(huì)頻譜接入方案 [J]. 北京: 計(jì)算機(jī)工程與設(shè)計(jì),2011, 32(4): 1182-1185.

LI Xiaoya, ZHANG Youguang, WU Huasen. POMDP based dynamic spectrum access algorithm in cognitive radio[J]. Beijing: Computer Engineering and Design, 2011, 32(4): 1182-1185. (in Chinese)

[7] FETTE B A. Congnitive Radio Technology[M]. Salt Lake City: Academic Press, 2009.

[8] ZHAO Qing, SADLER B M. A survey of dynamic spectrum access signal processing, networking, and regulatory policy[J]. IEEE Signal Processing Magazine, 2007, 24: 79-89.

[9] GEIRHOFER S, TONG L, SADLER B M, Dynamic spectrum access in WLAN channels: empirical model and its stochastic analysis[C], Boston: in Proc. of the First International Workshop on Technology and Policy in Accessing Spectrum (TAPAS), 2006.

[10] CASSANDRA A R. EXACT AND APPROXIMATE ALGORITHMS FOR PARTIALLY OBSERVABLE MARKOV DECISION PROCESSES[D], Ph. D., Providence: Brown University, 1998.

[11] SPAAN M T J, VLASSIS N. Perseus: Randomized Point-based Value Iteration for POMDPs[J], Journal of Artificial Intelligence Research, California: AAAI Press, 2005, 24: 195-22.

[12] ZHANG N L, ZHANG W. Speeding up the convergence of value iteration in partially observable Markov decision processes[J]. Journal of Artificial Intelligence Research, California: AAAI Press, 2001, 14: 29-51.

[13] SONDIK E J, The optimal control of partially observable Markov decision processes[D]. Ph. D., Stanford: Stanford University, 1971.

[14] 胡奇英，劉建庸，馬爾科夫決策過(guò)程引論[M]，西安：西安電子科技大學(xué)出版社，2000.