朱　江，陳紅翠，熊加毫

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

基于賭博機模型的非時隙信道選擇機制*

朱江，陳紅翠，熊加毫

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

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

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

0　引言

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

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

1　系統(tǒng)模型

1.1信道模型

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

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

圖1　非時隙信道模型

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

1.2效用函數(shù)

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

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

1.3干擾概率

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

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

所以干擾概率表示為：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4　仿真分析

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

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

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

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

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

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

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

5　結(jié)論

本文中應(yīng)用RMAB模型來搭建未知信息參數(shù)的網(wǎng)絡(luò)系統(tǒng)，然后通過EMA算法實現(xiàn)用戶對系統(tǒng)內(nèi)信道使用情形的初步學(xué)習(xí)，然后借助Q學(xué)習(xí)算法實現(xiàn)了RMAB模型下的Gittins索引值求解，制定出了認(rèn)知用戶的信道選擇策略，同時又能通過不斷學(xué)習(xí)更新自身策略，最終實現(xiàn)系統(tǒng)內(nèi)信道資源的充分使用，以及保證認(rèn)知用戶對主用戶通信干擾的可控性。最終，仿真實驗從多方面證明本文提出的選擇機制能夠很好地提高系統(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].計算機應(yīng)用研究，2013，30(5)：1467-1470.

[3]劉振坤，鮮永菊.認(rèn)知網(wǎng)絡(luò)中基于競價模型的頻譜分配研究[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

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

2015-09-11)

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

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

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

中文引用格式：朱江，陳紅翠，熊加毫.基于賭博機模型的非時隙信道選擇機制[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.