基于Q-Learning的機會頻譜接入算法

范文翰 趙旦峰

摘要 針對認知無線電在動態(tài)信道業(yè)務(wù)特征場景下的機會頻譜接入問題進行研究。將Q-Learning理論應(yīng)用于頻譜接入問題，提出一種基于Q-Learning的適用于動態(tài)信道業(yè)務(wù)特征的機會頻譜接入算法。該算法中認知用戶通過與外部環(huán)境進行交互和迭代來獲取信息，從而選擇適當?shù)慕尤氩呗詠斫档皖l譜沖突率。通過將Q-Learning中學(xué)習(xí)速率設(shè)置為動態(tài)變化值，使得算法可以在外部環(huán)境特征發(fā)生改變后快速地再次收斂。仿真結(jié)果表明，該算法可以使認知用戶在頻譜環(huán)境未知的情況下選擇更加空閑的頻段，有效降低頻譜沖突率，同時明顯提高了動態(tài)信道業(yè)務(wù)特征場景下的收斂速度。

【關(guān)鍵詞】認知無線電 機會頻譜接入 Q學(xué)習(xí)沖突 概率

1 引言

近些年來，隨著技術(shù)和經(jīng)濟水平的不斷提升，人們對于無線通信業(yè)務(wù)的需求不斷增長，造成了頻譜資源緊缺的情況，為了解決這一問題，專家學(xué)者提出了認知無線電概念。機會頻譜接入（opportunistic spectrum access，OSA）是認知無線電系統(tǒng)的關(guān)鍵技術(shù)之一，其核心思想是認知網(wǎng)絡(luò)中的認知用戶可以在授權(quán)頻段未被授權(quán)用戶使用的情況下機會地接入該授權(quán)頻段。通過對時間、頻域、空域三維空間內(nèi)的大量空閑頻譜資源的利用，認知無線電技術(shù)可以顯著地提高頻譜資源的利用率。

機會頻譜接入技術(shù)的研究難點是認知用戶如何在信道環(huán)境先驗知識未知的情況下接入合適的頻段。為了解決這一問題，文獻[2]將Q學(xué)習(xí)算法應(yīng)用到機會頻譜接入中，文獻[3]提出一種基于雙動作0學(xué)習(xí)算法的接入方案，文獻[4]通過將Q學(xué)習(xí)算法和拍賣算法結(jié)合提高了算法的效率。但是這些算法都沒有考慮當信道環(huán)境特征發(fā)生改變后算法的收斂問題，因此本文在上述算法的基礎(chǔ)上，提出一種適用于動態(tài)信道特征的Q-Learning頻譜接入算法，使認知用戶可以在信道環(huán)境特征發(fā)生改變后可以重新迅速收斂。

2 系統(tǒng)模型

在認知網(wǎng)絡(luò)中，系統(tǒng)內(nèi)部存在多個授權(quán)用戶，授權(quán)用戶將根據(jù)自己的需求占用某些授頻帶，頻段的占用狀態(tài)隨著時間而改變。如圖1所示，在認知網(wǎng)絡(luò)中，當某個頻段暫時沒有被授權(quán)用戶使用時，認知用戶就可以抓住這個機會利用該頻段來進行通信，當授權(quán)用戶重新占用這段頻譜后，認知用戶需要迅速停止在該頻段上的通信業(yè)務(wù)以避免干擾授權(quán)用戶的通信。

3 基于0-Learning的機會頻譜接入算法

3.1 Q-Learning理論

Q學(xué)習(xí)（Q-Leaming）算法是一種重要的無模型強化學(xué)習(xí)算法，由Watkins在1989年提出。Q-Learning將智能體與外部環(huán)境交互的過程看作為一個馬爾科夫決策過程（ Markov DecisionProcesses，MDP），即未來狀態(tài)的概率分布不受歷史狀態(tài)影響，只和當前狀態(tài)相關(guān)。決策者只以當前狀態(tài)為依據(jù)來制定合適的策略。對于未知環(huán)境下的決策問題，馬爾可夫決策過程有一套統(tǒng)一的模型，其模型一般可以用四元組來表示。其中，S表示智能體所處外部環(huán)境的狀態(tài)集合;A表示智能體可以執(zhí)行的動作集;T為系統(tǒng)的狀態(tài)轉(zhuǎn)移函數(shù)，通常用T：AxS→P（s'|s，a）來表示智能體在執(zhí)行了動作a∈A后，狀態(tài)從s∈S轉(zhuǎn)移到s∈S的概率;R代表回報，即智能體執(zhí)行動作a之后從外部環(huán)境獲得的收益，正數(shù)表示正收益，負數(shù)表示負收益。

在Q-leaming算法中，智能體通過不斷與環(huán)境交互來獲取信息從而制定更優(yōu)的策略，即在每一次迭代過程中，智能體的目的就是根據(jù)當前狀態(tài)尋找能夠最大化期望的長期累積回報的動作，如式（2）所示為長期累積回報的最大值：

3.2.1 問題映射

算法將O學(xué)習(xí)理論應(yīng)用于認知網(wǎng)絡(luò)中，因此將認知用戶的資源調(diào)度過程建模為一個有限馬爾可夫決策過程（MDP），其中主要包括狀態(tài)空間S、動作空間A、即時回報r等等。

（1）狀態(tài)空間S：S={s1，S2，…，S_k}表示當前認知用戶可以使用的所有頻段，當認知用戶狀態(tài)為Sl時表示認知用戶此時占用第i個頻段。

（2）動作空間A：A={a1，a2，…a_k）表示認知用戶可以執(zhí)行的動作集合。動作空間A由k個動作構(gòu)成，表示k個可用頻段，認知用戶執(zhí)行動作a_i表示認知用戶將占用頻段i，同時智能體進入狀態(tài)s.。

（3）即時回報r：回報值r體現(xiàn)環(huán)境對認知用戶的反饋。算法主要目的是降低認知用戶與授權(quán)用戶之間的沖突率，即時回報r主要體現(xiàn)主次用戶之間的沖突情況，其表達式為：

（4）學(xué)習(xí)速率：在一般的0學(xué)習(xí)算法中，學(xué)習(xí)速率α的值將隨著Q值得迭代逐漸變小，這種方法既可以使Q學(xué)習(xí)初期擁有更快的學(xué)習(xí)速率，又可以避免產(chǎn)生不成熟收斂。但是當環(huán)境的特征發(fā)生改變時，算法需要重新收斂，在學(xué)習(xí)速率較小的情況下，算法的收斂速度將很慢。為了解決這個問題，提出了適用于動態(tài)環(huán)境特征的Q-Learning算法，算法將學(xué)習(xí)速

率α設(shè)置為動態(tài)值，其表達式為：

a=l/（1+arr（s，a）） （6）

其中arr（s，a）為智能體到達狀態(tài).動作對（s，a）的次數(shù)，每當智能體到達該狀態(tài).動作對一次，并且環(huán)境產(chǎn)生正反饋時，arr（s，a）的值將增加，而當環(huán)境產(chǎn)生負反饋時，arr（s，a）將以指數(shù)形式遞減。因此，隨著迭代的不斷進行，arr（s，a）的值不斷增加，相應(yīng)的α將不斷減小，算法逐漸以概率1收斂于最優(yōu)狀態(tài)，若環(huán)境特征突然改變，訪問（s，a）狀態(tài)對將獲得環(huán)境的負反饋，arr（s，a）的值將變小，隨著訪問次數(shù)和負反饋次數(shù)的增多，arr（s，a）的值將迅速減小，使得u迅速增大，算法將重新?lián)碛懈斓膶W(xué)習(xí)速率并快速收斂于新的狀態(tài)。

3.2.2 Boltzmann學(xué)習(xí)規(guī)則

擁有學(xué)習(xí)能力的認知用戶以0值表為依據(jù)選擇最優(yōu)策略，其最優(yōu)策略一般是最大化長期累積回報，即選擇擁有最大0值得動作。在算法迭代初期，智能體需要通過不斷地試探來對環(huán)境進行探索，當智能體獲得了足夠的信息后就可以對這些信息進行利用。探索可以使用戶訪問更多的狀態(tài)，增加用戶獲得更多長期回報的可能性，而利用可以使認知用戶選擇最優(yōu)的策略來增加其長期回報。但是這種方法存在一定問題，當智能體對環(huán)境的探索不夠完全時，算法有可能收斂于錯誤的狀態(tài)。為了避免這種情況的發(fā)生，Q學(xué)習(xí)要求智能體能夠盡可能多地訪問每個狀態(tài).動作對，因此認知用戶在制定策略的時候不能簡單地選擇最大0值對應(yīng)的動作。算法將采用Boltzmann學(xué)習(xí)規(guī)則，智能體根據(jù)Q值大小以不同的概率選擇各個動作，即Q值大的動作被選中的概率大，Q值小的動作也有較小的可能被選中，其概率表達式為：

其中P（a./s）表示認知用戶在狀態(tài)s下選擇動作a_i的概率，T是溫度系數(shù)，表示Q值大小對概率的影響程度。T較大時Q值對概率的影響較小，不同0值對應(yīng)的概率相差較小，當T較小時，Q值變化會對概率產(chǎn)生比較明顯的影響。算法將根據(jù)退火原理使溫度系數(shù)T隨著迭代次數(shù)的增加不斷減小，在算法迭代初期即使某個Q值較大也不會產(chǎn)生用戶只選擇該Q值對應(yīng)的動作的情況，而隨著迭代不斷進行，用戶對外部環(huán)境的探索逐漸完善，此時的T值較小，Q值相差較大的動作之間對應(yīng)的概率也有較大差距，用戶選擇較大Q值的概率將明顯高于選擇較小Q值的概率。通過引入Boltzmann學(xué)習(xí)規(guī)則可以使智能體從探索階段逐漸過渡到利用階段。

3.2.3 算法流程

算法的具體流程為：

步驟1：初始化Q值表、迭代次數(shù)t，arr（s，a）值、折現(xiàn)因子γ、溫度T等參數(shù)，隨機選擇初始狀態(tài)sO;

步驟2：觀察當前所處狀態(tài)s.，根據(jù)當前Q值表和式（8）計算各動作執(zhí)行概率并依據(jù)得到的概率選擇動作a.;

步驟3：感知模塊對頻段i進行偵測判斷此時頻段i是否空閑，若空閑進入步驟4，若繁忙進入步驟5;

步驟4：執(zhí)行動作a_i，并傳遞環(huán)境的回報值r，進入步驟6;

步驟5：計算沖突概率，并傳遞環(huán)境的回報值r，進入步驟6;

步驟6：根據(jù)式（5）更新Q值，根據(jù)環(huán)境的反饋更新arr（s，a）值，更新狀態(tài)為s，t加l;

步驟7：判斷t是否滿足結(jié)束條件，若不滿足，進入步驟2，若滿足則算法結(jié)束。

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

為了驗證算法的有效性，本文將對三種Q-Leaming算法分別在靜態(tài)信道業(yè)務(wù)特征和動態(tài)信道業(yè)務(wù)特征兩種場景進行仿真對比，三種算法分別為α遞減、a=0.5以及本文所提出的α動態(tài)變化的Q-Learning算法。仿真長度為20000個時隙，認知用戶在每個時隙根據(jù)Q值表以不同概率接入某一頻段，即每個時隙是認知用戶的一個迭代過程，認知用戶迭代20000次后停止仿真。為了便于分析，將20000個時隙分為40個相等的學(xué)習(xí)階段統(tǒng)計認知用戶與授權(quán)用戶的沖突概率，同時采用蒙特卡洛實驗策略，每個時隙將進行100次相互獨立的實驗并取其平均值為最后的實驗結(jié)果。

基于Q-Learning的頻譜接入算法的參數(shù)設(shè)計如下：頻段個數(shù)m=6，靜態(tài)信道業(yè)務(wù)特征場景下的頻段的業(yè)務(wù)負載分別為l，1，0.7，0.5，0.3，0.05，動態(tài)信道業(yè)務(wù)特征場景下的頻段的業(yè)務(wù)負載變化規(guī)律如表1所示。為了體現(xiàn)長期回報對策略選擇的重要性，設(shè)置折現(xiàn)因子γ=0.8。算法將采用Boltzmann學(xué)習(xí)規(guī)則，設(shè)置其初始溫To=l×l0⁵⁰，終止溫度Tend=l，溫度To將隨著迭代次數(shù)增加以參數(shù)為0 9的指數(shù)規(guī)律逐漸遞減，直到減小至終止溫度后停止遞減。

圖2為信道業(yè)務(wù)特征保持恒定的情況下三種Q學(xué)習(xí)算法下的主次用戶間的沖突概率，可以明顯看出三種Q學(xué)習(xí)都在大約第四個統(tǒng)計階段收斂。但是當a=0.5恒定不變時，沖突概率收斂于0.2左右，遠遠高于另外兩者，說明出現(xiàn)不成熟收斂。在靜態(tài)的信道業(yè)務(wù)特征的情況下，α遞減和動態(tài)α兩種Q學(xué)習(xí)算法的性能表現(xiàn)幾乎相同，二者的沖突概率幾乎同時收斂于0.1。

圖3為動態(tài)信道業(yè)務(wù)特征下的三種Q學(xué)習(xí)算法下的沖突概率，通過對比三種算法可知表現(xiàn)最差的是α遞減的Q學(xué)習(xí)算法，當信道特征發(fā)生改變后，其主次用戶的沖突概率激增至1，而且在接下來的迭代過程中沖突概率并沒有呈現(xiàn)迅速降低的趨勢，直到第三十個統(tǒng)計階段后沖突概率才開始下降至收斂值，這是因為迭代多次后，α的值遞減至較小的值，算法的學(xué)習(xí)速率將變得很低，在信道特征改變后算法無法快速學(xué)習(xí)新的環(huán)境知識。而α=0.5的Q學(xué)習(xí)算法在信道特征改變后主次用戶的沖突概率并沒有出現(xiàn)比較明顯的增加，這是因為α=0.5的Q學(xué)習(xí)學(xué)習(xí)速率較大，能夠迅速學(xué)習(xí)新的環(huán)境知識，但是固定較大的α值使認知用戶偏向于選擇一些迭代初期Q值較大的動作，即認知用戶并沒有遍歷全部的狀態(tài)，錯過了更優(yōu)的動作，造成算法的不成熟收斂，其沖突概率維持在0.2左右高于正常的最低沖突概率0.1。相比于這兩種0學(xué)習(xí)算法，α動態(tài)變化的Q學(xué)習(xí)算法首先可以將主次用戶的沖突概率迅速降低至0.1左右，并且能夠在信道特征發(fā)生改變后迅速收斂至新的概率值。因此在信道業(yè)務(wù)特征動態(tài)變化的情況下，α動態(tài)變化的Q學(xué)習(xí)算法要明顯優(yōu)于α恒定和α遞減的Q學(xué)習(xí)算法。

5 結(jié)論

本文針對動態(tài)信道業(yè)務(wù)特征情景下0學(xué)習(xí)的收斂問題提出了一種基于Q-Leaming的機會頻譜接入算法，通過令學(xué)習(xí)速率α以一定規(guī)律動態(tài)變化的方式使算法能夠適用于信道業(yè)務(wù)動態(tài)變化的場景。仿真結(jié)果表明，當頻段的業(yè)務(wù)特征發(fā)生改變后，算法可以迅速收斂于最優(yōu)策略，即認知用戶與授權(quán)用戶的頻譜沖突率最低。

參考文獻

[l]Mitola J I，Maguire G Q J.Cognitiveradio： making software radiosmore personal [J]. IEEE PersCommun， 1999，6 （04）： 13-18.

[2] Alsaleh 0，Hamdaoui B，F(xiàn)ern A.Q-learning for opportunistic spectrumaccess [C]. Interna tional

Wireles sCommunications and Mobile ComputingConference. ACM， 2010： 220-224.

[3]吳啟暉，劉瓊俐，基于DAQL算法的動態(tài)頻譜接八方案[J].解放軍理工大學(xué)學(xué)報：自然科學(xué)版，2008，9 （06）： 607-611.

[4] Chen Z，Qiu R C.Q-learning basedbidding algorithm for spectrumauction in cognitive radio [C].Southeas tcon，2011

Proceedings ofIEEE. IEEE， 2011： 409-412.

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

[6]Watkins C J C H.Learning from DelayedRewards [J]. Robotics & Au tonomousSystems，1989，15 （04）： 233-235.

[7]桂林，武小悅.部分可觀測馬爾可夫決策過程算法綜述[J]，系統(tǒng)工程與電子技術(shù)，2008， 30 （06）：1058-1064.

[8] Kaelbling L P，Littman M L，MooreA W. Reinforcement Learning：ASurvey[J]. J Artificial IntelligenceResearch，1996，4（01）：237-285.

[9] Gosavi A. Reinforcement Learning：A Tutorial Survey and RecentAdvances [J]. Informs Journal onComputing， 2009， 21 （02） ： 178-192.

[lO]Guo M，Liu Y，Malec J.A new Q-learningalgorithm based on the metropoliscriterion. [J]. IEEE Transactions onSystems Man & Cybernetics PartCybernetics A Publication of theIEEE Systems Man & CyberneticsSociety， 2004， 34 （05）： 2140.