朱　江，陳紅翠，熊加毫

（重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065）

基于賭博機(jī)模型的非時(shí)隙信道選擇機(jī)制*

朱江，陳紅翠，熊加毫

（重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065）

針對(duì)未知信息環(huán)境網(wǎng)絡(luò)中信道資源的選擇與分配問(wèn)題，提出了一種新的信道選擇機(jī)制。借助于無(wú)休止多臂賭博機(jī)模型搭建網(wǎng)絡(luò)系統(tǒng)模型，通過(guò)最大期望算法(EMA)實(shí)現(xiàn)了未知環(huán)境下對(duì)非時(shí)隙信道使用情況的初步學(xué)習(xí)，借助Q學(xué)習(xí)算法實(shí)現(xiàn)無(wú)休止多臂賭博機(jī)模型下的Gittins索引值的求解，同時(shí)確定出在一定干擾約束下的最優(yōu)信道選擇策略，最后通過(guò)借助拍賣(mài)機(jī)制實(shí)現(xiàn)系統(tǒng)內(nèi)認(rèn)知用戶(hù)之間信道選擇的沖突。經(jīng)仿真實(shí)現(xiàn)驗(yàn)證，提出的新信道選擇機(jī)制能夠很好地避免認(rèn)知用戶(hù)對(duì)主用戶(hù)的干擾，使系統(tǒng)中的信道得到高效利用，系統(tǒng)通信量得到大幅提高。

干擾約束；Gittins索引值；Q學(xué)習(xí)；無(wú)休止多臂賭博機(jī)

0　引言

隨著無(wú)線(xiàn)網(wǎng)絡(luò)飛速發(fā)展和頻譜資源需求劇增，以及無(wú)線(xiàn)環(huán)境逐步變復(fù)雜，使得無(wú)線(xiàn)網(wǎng)絡(luò)系統(tǒng)中的非授權(quán)用戶(hù)想要獲得完整的網(wǎng)絡(luò)環(huán)境的參數(shù)信息變得愈加困難。因此，對(duì)于非完全信息以致未知環(huán)境無(wú)線(xiàn)網(wǎng)絡(luò)中的資源分配問(wèn)題的研究已經(jīng)成為解決當(dāng)前網(wǎng)絡(luò)困境的主要研究方向之一。目前主要應(yīng)用于未知網(wǎng)絡(luò)環(huán)境下資源分配的理論是部分可觀測(cè)馬爾科夫(Partially Observable Markov Decision Process，POMDP)以及隱馬爾科夫模型(Hidden Markov Model，HMM)。文獻(xiàn)[1]中將網(wǎng)絡(luò)環(huán)境搭建為未知環(huán)境情形，首先通過(guò)最大似然算法實(shí)現(xiàn)網(wǎng)絡(luò)中信道使用情形的預(yù)測(cè)，然后借助POMDP模型實(shí)現(xiàn)了網(wǎng)絡(luò)系統(tǒng)中多信道接入問(wèn)題。文獻(xiàn)[2]為基于未知信息環(huán)境認(rèn)知網(wǎng)絡(luò)中頻譜分配問(wèn)題，使用Q學(xué)習(xí)算法機(jī)會(huì)式頻譜接入的研究。文獻(xiàn)[5]將POMDP模型與Q學(xué)習(xí)算法相結(jié)合構(gòu)建了分布式認(rèn)知網(wǎng)絡(luò)中的MAC協(xié)議，使網(wǎng)絡(luò)系統(tǒng)中的信道資源得以合理、有效的利用。

現(xiàn)今基于RMAB或者M(jìn)AB模型的無(wú)線(xiàn)資源分配方法存在兩方面局限性：一是對(duì)于復(fù)雜型網(wǎng)絡(luò)系統(tǒng)研究較少，尤其是信道模型大多只采用簡(jiǎn)單的0-1模型進(jìn)行研究；二是對(duì)于存在條件限制的MAB模型研究較少。因此，本文采用了不分時(shí)隙的 ON-OFF信道模型，并考慮了系統(tǒng)內(nèi)的干擾限制以及認(rèn)知用戶(hù)的感知誤差等因素，然后借助Q學(xué)習(xí)算法實(shí)現(xiàn)Gittins索引值算法的求解。最后，通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了提出的信道選擇機(jī)制的合理性以及優(yōu)越性。

1　系統(tǒng)模型

1.1信道模型

假設(shè)由N個(gè)獨(dú)立的認(rèn)知用戶(hù)組成一個(gè)認(rèn)知無(wú)線(xiàn)網(wǎng)絡(luò)，且每個(gè)用戶(hù)均不知其他用戶(hù)的存在。在此網(wǎng)絡(luò)中所有的用戶(hù)共用M個(gè)信道，并且在無(wú)線(xiàn)網(wǎng)絡(luò)環(huán)境中，由于衰落、干擾以及用戶(hù)地理位置的差異導(dǎo)致不同信道對(duì)同一用戶(hù)的質(zhì)量不相同。信道的質(zhì)量矩陣表示為，用戶(hù)集合N={1，…，N}，信道集合表示為M={1，…，M}，且1≤M≤N。信道的ON狀態(tài)和OFF狀態(tài)交替出現(xiàn)，并且分別服從均值為和的指數(shù)分布，信道間相互獨(dú)立，主用戶(hù)占用信道的平均概率則可以表示為：P0=μi/(λi+μi)，信道空閑的平均概率則為：P1=λi/(λi+μi)。

信道模型和感知模型如圖1所示，設(shè)時(shí)隙長(zhǎng)度為T(mén)，感知模塊的時(shí)間為τ。為方便展示，圖中只描述了一個(gè)認(rèn)知用戶(hù)的感知情形。

圖1　非時(shí)隙信道模型

假設(shè)認(rèn)知用戶(hù)采用能量感知形式進(jìn)行信道可用性感知。認(rèn)知用戶(hù)感知階段接收到的信道表示為：

1.2效用函數(shù)

系統(tǒng)的值函數(shù)表示為：

其中 ωn，i(t)表示當(dāng)前信道空閑的概率，Bn，i表示用戶(hù)n使用信道i時(shí)的信道帶寬，(T-τ)表示信道空閑時(shí)認(rèn)知用戶(hù)傳輸?shù)臅r(shí)間長(zhǎng)度，ωn，i(t)exp(-λiT)表示信道空閑且時(shí)間持續(xù)為T(mén)的概率。在此需要針對(duì)不同的用戶(hù)找到相應(yīng)的最優(yōu)策略ρ*：

1.3干擾概率

因?yàn)檎J(rèn)知用戶(hù)對(duì)網(wǎng)絡(luò)環(huán)境中主用戶(hù)的行為是未知的，且信道狀態(tài)在感知階段不發(fā)生變化，只在認(rèn)知用戶(hù)傳輸階段改變。則有感知階段信道狀態(tài)為0，且持續(xù)時(shí)間T的概率為：

同理信道狀態(tài)感知為1，但是在認(rèn)知用戶(hù)傳輸中主用戶(hù)存在(狀態(tài)0)的概率為：

所以干擾概率表示為：

2　信道參數(shù)學(xué)習(xí)算法

圖2所描述的是認(rèn)知用戶(hù)節(jié)點(diǎn)的不規(guī)則采樣圖。

圖2　認(rèn)知用戶(hù)無(wú)規(guī)律采樣圖示

將連續(xù)時(shí)間馬爾科夫鏈的參數(shù)估計(jì)問(wèn)題轉(zhuǎn)換為離散時(shí)間的馬爾科夫參數(shù)估計(jì)問(wèn)題，然后采用最大期望算法(Expectation-Maximization Algorithm，EMA)實(shí)現(xiàn)參數(shù)估計(jì)。

對(duì)式(10)取對(duì)數(shù)可以得出：

由對(duì)數(shù)公式可知，如果S=1則轉(zhuǎn)移矩陣估計(jì)可以直接由數(shù)學(xué)公式求出，但是在本系統(tǒng)中使用的S遠(yuǎn)遠(yuǎn)大于1，所以提出使用EMA算法實(shí)現(xiàn)轉(zhuǎn)移矩陣的估計(jì)。

假定第l次的E步操作中獲得P的對(duì)數(shù)似然估計(jì)值表示為 P(l)，此時(shí)的采樣值(非完全數(shù)據(jù))仍表示為 Z，Y為未完全觀測(cè)值Z構(gòu)建的一個(gè)完全的數(shù)據(jù)陣，則在l+ 1次的E步操作中的計(jì)算表示為：

則第l+1次的M步操作計(jì)算出的矩陣估計(jì)值為：

通過(guò)式(11)、式(12)及式(10)的對(duì)數(shù)形式可以得出P(l+1)的迭代表示形式(具體推導(dǎo)過(guò)程可參見(jiàn)文獻(xiàn)[6])：

其中有 i，j=0，1，并且 Nij(P(l))可由下式得出：

綜上可知，通過(guò)已知的未完全觀測(cè)數(shù)據(jù)以及設(shè)定初始的轉(zhuǎn)移矩陣 P(0)、算法收斂條件 ε，然后經(jīng)過(guò)式(13)和式(14)不斷迭代直至最終收斂，可得出轉(zhuǎn)移矩陣的估計(jì)值P。

3　基于Q學(xué)習(xí)算法Gittins索引值計(jì)算

具體的Q學(xué)習(xí)算法的操作步驟如下：

(1)初始化用戶(hù)的 Qn=(si，t，an，i，t)=0；

(2)每個(gè)用戶(hù)在時(shí)隙感知階段以概率 Pt(n，i)隨機(jī)地選擇所要感知的信道，其中：

其中T表示波爾茲曼干擾溫度系數(shù)。

根據(jù)文獻(xiàn)[8]提出的結(jié)論，可以得出此過(guò)程中狀態(tài) x的Gittins索引值為：

(3)用戶(hù) n以 Pt(n，i)的概率的大小排序各個(gè)信道并從中選擇一個(gè)或者多個(gè)信道進(jìn)行感知，根據(jù)感知結(jié)果用戶(hù)制定相應(yīng)的行為策略去更新不同行為下的 Qn(si，t，an，i，t)，計(jì)算信道在不同行為下的 Gittins索引值，并選擇對(duì)其中索引值最大的一個(gè)或者多個(gè)信道進(jìn)行接入、傳輸數(shù)據(jù)，然后根據(jù)立即回報(bào)值，更新各自的Q值：

其中，vni表示為用戶(hù)n對(duì)信道i的學(xué)習(xí)因子，其數(shù)學(xué)公式表示為：

ωn，i，t表示為用戶(hù) n對(duì)信道 i空閑的信任概率值，其更新公式：

(4)如果對(duì)于任意的信道 i(i∈M)，有Pt(n，i)≥0.99，則此學(xué)習(xí)過(guò)程退出，否則繼續(xù)步驟(2)，并以此進(jìn)行其后操作。

4　仿真分析

為驗(yàn)證本文提出的選擇機(jī)制的優(yōu)越性，設(shè)定了兩種常用算法進(jìn)行比較：?jiǎn)我坏腝學(xué)習(xí)算法選擇機(jī)制以及RMAB模型下常用的UCB算法。設(shè)定系統(tǒng)中信道數(shù)為10，用戶(hù)數(shù)為4，并且不同時(shí)隙用戶(hù)根據(jù)需求調(diào)整自己的選擇信道的數(shù)目，使得系統(tǒng)內(nèi)用戶(hù)能夠?qū)崿F(xiàn)多信道接入(考慮到實(shí)際系統(tǒng)條件限制，設(shè)定每個(gè)用戶(hù)最多選擇信道數(shù)位3)。信道參數(shù)T=0.25 s，τ=0.01，β=0.95，用戶(hù)數(shù)為3～15。

圖3顯示在用戶(hù)數(shù)為N=9時(shí)，不同沖突約束、不同算法中用戶(hù)獲得平均吞吐量的變化。從圖中可以看出本文提出的信道選擇機(jī)制能夠很好地處理認(rèn)知用戶(hù)與主用戶(hù)之間的沖突，使網(wǎng)絡(luò)中各用戶(hù)之間充分的使用信道資源，實(shí)現(xiàn)系統(tǒng)通信量的提升。同時(shí)，因?yàn)闆_突約束越小用戶(hù)選擇信道的概率越小致使信道使用不充分，隨著沖突約束的提升在保證用戶(hù)選擇的同時(shí)能夠有效的避免與主用戶(hù)的沖突，所以取15%作為系統(tǒng)沖突的限制，既能夠保證認(rèn)知用戶(hù)選擇，同時(shí)又能不對(duì)主用戶(hù)通信造成干擾。

圖4顯示了不同算法中采用不同認(rèn)知用戶(hù)數(shù)時(shí)系統(tǒng)內(nèi)信道利用率的變化，從圖中可以看出本文提出的算法能夠取得很好的信道利用率。隨著認(rèn)知用戶(hù)的不斷增大，當(dāng)用戶(hù)數(shù)超過(guò)系統(tǒng)承受能力之后系統(tǒng)中認(rèn)知用戶(hù)之間會(huì)產(chǎn)生沖突，同時(shí)用戶(hù)通信需求的擴(kuò)大也會(huì)對(duì)主用戶(hù)的通信造成影響，致使系統(tǒng)內(nèi)信道使用率會(huì)有一定下降。

圖3　不同沖突約束下的系統(tǒng)平均吞吐量的變化

圖4　不同算法中不同用戶(hù)數(shù)對(duì)應(yīng)的信道使用率變化

圖5顯示的是在系統(tǒng)中干擾限制以認(rèn)知用戶(hù)數(shù)目固定的條件下(N=9，Imax=0.20)，隨著系統(tǒng)中信道數(shù)的變化，認(rèn)知用戶(hù)與主用戶(hù)產(chǎn)生干擾沖突的變化情況。從圖中可以看出，本文提出的機(jī)制能夠在較小范圍內(nèi)控制認(rèn)知用戶(hù)的信道選擇，盡量避免與主用戶(hù)的通信產(chǎn)生干擾，從圖中可以看出隨著系統(tǒng)中信道數(shù)目的增大，認(rèn)知用戶(hù)對(duì)主用戶(hù)的干擾逐漸減小，也就是系統(tǒng)中認(rèn)知用戶(hù)選擇信道的范圍增大，選擇空閑信道的概率增大。

圖5　不同信道數(shù)對(duì)應(yīng)的沖突率變化

5　結(jié)論

本文中應(yīng)用RMAB模型來(lái)搭建未知信息參數(shù)的網(wǎng)絡(luò)系統(tǒng)，然后通過(guò)EMA算法實(shí)現(xiàn)用戶(hù)對(duì)系統(tǒng)內(nèi)信道使用情形的初步學(xué)習(xí)，然后借助Q學(xué)習(xí)算法實(shí)現(xiàn)了RMAB模型下的Gittins索引值求解，制定出了認(rèn)知用戶(hù)的信道選擇策略，同時(shí)又能通過(guò)不斷學(xué)習(xí)更新自身策略，最終實(shí)現(xiàn)系統(tǒng)內(nèi)信道資源的充分使用，以及保證認(rèn)知用戶(hù)對(duì)主用戶(hù)通信干擾的可控性。最終，仿真實(shí)驗(yàn)從多方面證明本文提出的選擇機(jī)制能夠很好地提高系統(tǒng)通信容量，使未知環(huán)境中的信道利用率得到明顯提升。

[1]Gao Yang，Wang Yiming.Multi-channel access algorithm with channel state information unknown[C].Intelligent Computation Technology and Automation(ICICTA)，2012 Fifth International Conference on.IEEE，2012：427-430.

[2]張凱，李鷗，楊白薇.基于Q-learning的機(jī)會(huì)頻譜接入信道選擇算法[J].計(jì)算機(jī)應(yīng)用研究，2013，30(5)：1467-1470.

[3]劉振坤，鮮永菊.認(rèn)知網(wǎng)絡(luò)中基于競(jìng)價(jià)模型的頻譜分配研究[J].計(jì)算機(jī)應(yīng)用研究，2010，27(3).

[4]Raschellà A，Pérez-Romero J，Sallent O，et al.On the use of POMDP for spectrum selection in cognitive radio networks[C]. Cognitive Radio Oriented Wireless Networks(CROWNCOM)，2013 8th International Conference on.IEEE，2013：19-24.

[5]LAN Z，JIANG H，WU X.Decentralized cognitive MAC protocol design based on POMDP and Q-Learning[C].IEEE International ICST Conference on Communication and Networking.2012：548-551.

[6]LAZAR N A.Statistical analysis with missing data[J]. Technometrics，2003，45(4)：364-365.

[7]GITTINS J，GLAZEBROOK K，WEBER R.Multi-armed bandit allocation indices[M].John Wiley&Sons，2011.

[8]CHAKRAVORTY J，MAHAJAN A.Multi-armed bandits，gittins index，and its calculation[J].Methods and Applications of Statistics in Clinical Trials：Planning，Analysis，and Inferential Methods，2013(2)：416-435.

A selection mechanism of un-slotted channel based on multi-armed bandit

Zhu Jiang，Chen Hongcui，Xiong Jiahao
(College of Information and Communication Engineering，Chongqing University of Post and Telecommunication，Chongqing 400065，China)

A new channel selection mechanism was proposed for the problem that how to select and distribute the channels under the unknown environment.Use the restless multi-armed bandit model to build the network system.Then,learning the usage of the channels preliminary by the expectation-maximization algorithm under the unknown environment,and later,achieve the Gittins index of restless multi-armed bandit by using the Q learning.In the meantime,then,obtained the optimal policy of channels selection under the certain interference constraints.Last,this paper used the multi-bid auction to deal with the collision among the users. Finally,the simulation results demonstrate that,the new mechanism can be good to avoid the interference to the primary user,to make the usage of channels efficiently and to improve the traffic of the system greatly.

interference control；Gittins index policy；Q learning；restless multi-armed bandit

TN92

A

10.16157/j.issn.0258-7998.2016.01.024

國(guó)家自然科學(xué)基金項(xiàng)目(61102062)；重慶市科委自然科學(xué)基金項(xiàng)目(cstc2015jcyjA40050)；重慶市教委科學(xué)技術(shù)研究項(xiàng)目(KJ120530)

2015-09-11)

朱江(1977－)，男，博士，副教授，主要研究方向：認(rèn)知無(wú)線(xiàn)電。

陳紅翠(1989－)，通信作者，女，碩士研究生，主要研究方向：認(rèn)知無(wú)線(xiàn)電，E-mail：1271103552@qq.com。

熊加毫(1989－)，男，碩士研究生，主要研究方向：認(rèn)知無(wú)線(xiàn)電。

中文引用格式：朱江，陳紅翠，熊加毫.基于賭博機(jī)模型的非時(shí)隙信道選擇機(jī)制[J].電子技術(shù)應(yīng)用，2016，42(1)：91-94.

英文引用格式：Zhu Jiang，Chen Hongcui，Xiong Jiahao.A selection mechanism of un-slotted channel based on multi-armed bandit[J].Application of Electronic Technique，2016，42(1)：91-94.