基于量子遺傳模擬退火算法的認(rèn)知無(wú)線電頻譜分配方法研究

【摘要】 無(wú)線頻譜資源的緊張與無(wú)線通信應(yīng)用的激增之間的矛盾越來(lái)越突出，認(rèn)知無(wú)線電作為緩解頻譜資源緊張的重要途徑，其對(duì)應(yīng)的頻譜分配方法一直是研究的熱點(diǎn)。量子遺傳模擬退火算法是將量子遺傳算法的多點(diǎn)并行性搜索及模擬退火算法所具有的較強(qiáng)的單點(diǎn)串行搜索能力相融合，模擬退火算法作為一個(gè)算子引入到量子遺傳算法中能夠克服量子遺傳算法易產(chǎn)生的“早熟收斂”問(wèn)題，實(shí)現(xiàn)兩種算法的優(yōu)劣互補(bǔ)，該算法在求解優(yōu)化問(wèn)題時(shí)具有更強(qiáng)的搜索能力和效率，并獲得較高質(zhì)量的最優(yōu)解。本文將量子遺傳模擬退火算法應(yīng)用于認(rèn)知無(wú)線電頻譜分配問(wèn)題中，采用非合作博弈論模型，研究了多用戶競(jìng)爭(zhēng)多信道的頻譜分配方法，通過(guò)與已有的基于量子遺傳算法的頻譜分配性能進(jìn)行仿真比對(duì)，驗(yàn)證了該思路的可行性及優(yōu)勢(shì)。

【關(guān)鍵詞】 認(rèn)知無(wú)線電 頻譜分配 量子遺傳模擬退火算法 博弈論 多用戶多信道

Researching on spectrum allocation in Cognitive Radio Networks based on Quantum Genetic Simulated Annealing Algorithm

Xiao Chanchan

（CHINA MOBILE （SHENZHEN） LIMITED， Shenzhen， 518048， China）

Abstract： The contradiction between the tension of the wireless spectrum resources and the surge in wireless communication applications is becoming more and more prominent. The spectrum models and algorithms in Cognitive radio network which is an important way to ease the shortage of spectrum resources are always the focus. The integration of the multi-parallel searching capability of Quantum Genetic Algorithm（QGA）and the stronger single-point serial searching capability of Simulated Annealing Algorithm（SA）becomes Quantum Genetic Simulated Annealing Algorithm（QGSA），in which SA is an operator to overcome the premature convergence problem of QGA and complements each other. The algorithm has more powerful searching capabilities and efficiency， and can obtain higher quality solution in solving optimization problem. QGSA is applied to the cognitive radio spectrum allocation in this paper， which is based on non-cooperative game theory model. The spectrum allocation for multi-user and multi-channel is studied. The spectrum allocation performance between QGSA and QGA are compared， and the results verify the superiority of spectrum allocation based on QGSA.

Keywords： Cognitive radio network ， spectrum allocation ， Quantum Genetic Simulated Annealing Algorithm， Game Theory， multiuser multi-channel

一、引言

隨著無(wú)線通信的應(yīng)用大量增加，無(wú)線終端的數(shù)量激增，而且越來(lái)越多的移動(dòng)通信設(shè)備和通信服務(wù)的融合對(duì)更高的數(shù)據(jù)傳輸速率的需求日益增加，這造成對(duì)無(wú)線頻譜資源的需求量將達(dá)到前所未有的程度。而現(xiàn)實(shí)的問(wèn)題是，無(wú)線通信頻譜的利用效率并不高。在目前投入運(yùn)營(yíng)的無(wú)線頻段中，存在著許多“頻譜空洞”（未被利用的頻譜）[1]。

目前，認(rèn)知無(wú)線電頻譜分配模型和算法一直是國(guó)內(nèi)外研究熱點(diǎn)，既有經(jīng)典的頻譜分配，如圖論著色模型、博弈論模型[4][5]、拍賣競(jìng)價(jià)模型以及干擾溫度模型，這些傳統(tǒng)的頻譜分配算法取得了一定的研究成果，但是也存在諸如時(shí)間開銷大、系統(tǒng)效用低、頻譜利用率低等不足，為此，現(xiàn)已有很多文獻(xiàn)陸續(xù)提出將量子智能算法應(yīng)用于認(rèn)知無(wú)線電頻譜分配技術(shù)中，例如文獻(xiàn)[11][12]提出將量子遺傳算法應(yīng)用于認(rèn)知無(wú)線電頻譜分配博弈論模型中，并通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了該算法的優(yōu)勢(shì)。文獻(xiàn)[13]實(shí)現(xiàn)了將量子粒子群算法應(yīng)用于認(rèn)知無(wú)線電頻譜分配中，并與文獻(xiàn)[12]中的量子遺傳算法頻譜分配性能進(jìn)行了比對(duì)，這些研究都驗(yàn)證了量子智能算法應(yīng)用于認(rèn)知無(wú)線電頻譜分配研究的可行性和優(yōu)勢(shì)。本文在分析和探討已存在的基于QGA的認(rèn)知無(wú)線電頻譜分配的非合作博弈論模型的基礎(chǔ)上[12]，將頻譜分配的博弈論思想引入QGSA算法[14]中，提出基于QGSA算法的頻譜分配方法。首先通過(guò)對(duì)頻譜分配問(wèn)題的本質(zhì)進(jìn)行分析，給出了兩用戶和多用戶場(chǎng)景下的頻譜分配數(shù)學(xué)模型。其次，針對(duì)頻譜分配數(shù)學(xué)模型，給出了采用QGSA算法實(shí)現(xiàn)頻譜分配的詳細(xì)流程。最后，對(duì)認(rèn)知無(wú)線電網(wǎng)絡(luò)中基于QGA和QGSA的頻譜分配算法進(jìn)行仿真對(duì)比實(shí)驗(yàn)，并對(duì)仿真對(duì)比實(shí)驗(yàn)結(jié)果進(jìn)行了分析，從信道數(shù)量和用戶數(shù)量分別對(duì)頻譜分配結(jié)果的影響兩方面驗(yàn)證了基于QGSA算法的頻譜分配方法的有效性和優(yōu)越性。

二、頻譜分配算法設(shè)計(jì)

2.1頻譜共享場(chǎng)景

在圖1中，描述了1個(gè)主用戶PU和多個(gè)次用戶SU之間的頻譜共享場(chǎng)景。該場(chǎng)景中主用戶基站（發(fā)射機(jī)）通過(guò)自身的授權(quán)頻段發(fā)射數(shù)據(jù)給主用戶（接收機(jī)），其他的次用戶（接收機(jī)）對(duì)也企圖接入該授權(quán)頻段發(fā)射數(shù)據(jù)，另外主用戶也會(huì)接收到來(lái)自次用戶基站（發(fā)射機(jī)）發(fā)射的信號(hào)，對(duì)主用戶來(lái)講，這是干擾信號(hào)[7]。在該場(chǎng)景中的頻譜感知分配中心可以是一臺(tái)獨(dú)立的計(jì)算機(jī)或者基站，其主要功能是通過(guò)感知周圍主用戶的授權(quán)頻段的使用情況，實(shí)現(xiàn)“頻譜空洞”信息的收集，據(jù)此采用一定的頻譜分配方法來(lái)動(dòng)態(tài)地合理分配空閑的頻譜資源給這些企圖接入的次用戶來(lái)使用，同時(shí)對(duì)主用戶的通信造成干擾降到最低，達(dá)到頻譜資源的高效合理的利用。

2.2頻譜分配數(shù)學(xué)模型

2.2.1兩用戶場(chǎng)景

其中M為用戶總數(shù)，K為信道總數(shù)， Pi j表示第i個(gè)用戶在信道j上分配的功率。

采用的博弈論模型[13]為：G={M，{Fi，Pi}，{Ii}，{Ci}}，i=1，2，…，M，此博弈包括：

M：用戶總數(shù)，即為博弈的參與者數(shù)量。

Fi，Pi：分別表示用戶i的載頻集合和各個(gè)載頻上的分配功率集合，即博弈策略集合。

Ii：用戶i獲得的各個(gè)載頻上其他用戶帶來(lái)的干擾信息，即博弈論中的信息。

Ci：用戶i的效用函數(shù)，此處采用用戶i在各個(gè)信道上的信道容量和作為效用函數(shù)，代表博弈參與者的收益。

根據(jù)香農(nóng)定理C=Blog（1+SIR）可知，設(shè)帶寬均為B=1，用戶i的效用函數(shù)為：

通過(guò)以上分析可知，頻譜分配問(wèn)題實(shí)質(zhì)上是一個(gè)優(yōu)化問(wèn)題，可以從全局優(yōu)化的角度入手，根據(jù)其對(duì)應(yīng)的優(yōu)化問(wèn)題數(shù)學(xué)模型，采用QGSA優(yōu)化算法隨機(jī)性的進(jìn)行全局搜索，這也是QGSA算法求解優(yōu)化問(wèn)題的核心所在，它能夠在隨機(jī)性的全局搜索過(guò)程中自適應(yīng)地獲取搜索空間的信息并掌控搜索方向，以獲得優(yōu)化問(wèn)題的全局最優(yōu)解，所以可以采用QGSA實(shí)現(xiàn)對(duì)頻譜分配優(yōu)化問(wèn)題的求解。

2.3頻譜分配算法流程

1、量子染色體編碼。對(duì)于一個(gè)用戶在各個(gè)信道上分配的功率值被編碼為一個(gè)0和1組成的字符串，該字符串代表在該信道上的分配的功率值，所有信道上的0和1組成的字符串代表一條染色體（chromosome），這里采用每個(gè)信道的編碼長(zhǎng)度為10，那么對(duì)于K個(gè)信道的用戶，一條染色體的長(zhǎng)度length=10*K。那么將該用戶所有信道占用情況編碼為一條染色體表示為如圖3：

2、參數(shù)設(shè)置及種群初始化：量子遺傳操作的種群規(guī)模pop、用戶數(shù)量M、信道數(shù)量K、帶內(nèi)噪聲功率N，信道增益hii、hji，每個(gè)用戶發(fā)射功率的最大值Pmax、染色體編碼長(zhǎng)度length、進(jìn)化代數(shù)maxgen、量子變異概率Pv、轉(zhuǎn)角步長(zhǎng)Δθ；模擬退火操作的初始溫T、退火系數(shù)λ、每一固定溫度下的迭代次數(shù)為L(zhǎng)、更新解的概率Prenew、學(xué)習(xí)步長(zhǎng)step、搜索半徑sR。隨機(jī)生成初始化種群Q（t）。

3、觀察測(cè)量種群Q（t）的狀態(tài)：對(duì)于任一染色體的任一基因，隨即產(chǎn)生一個(gè)0～1之間的數(shù)，如果該數(shù)大于該基因的 2α，則測(cè)量結(jié)果為1，否則為0，生成二進(jìn)制解集P（t0）。

4、評(píng)估P（t）的效用函數(shù)值，兩用戶兩信道的效用函數(shù)為式（2.3）。

5、記錄P（t）中最佳效用函數(shù)值及對(duì)應(yīng)種群中的最佳用戶作為下一步種群更新的目標(biāo)。

6、對(duì)當(dāng)代的種群進(jìn)行量子交叉、更新和變異，得到子代Q（t+1）。量子交叉：采用全干擾交叉[14]。

表中xi和bi是當(dāng)前染色體和當(dāng)前最優(yōu)染色體的第i位，f（·）表示適應(yīng)度函數(shù)值，Δθ和S（αi，βi）分別表示θi的大小、方向，即θi=Δθ·S（αi，βi）。

量子變異：通過(guò)量子非門實(shí)現(xiàn)的，具體操作如下：

1）以某一概率值從當(dāng)前種群中選擇若干個(gè)體作為變異對(duì)象；

其中jiP→表示由當(dāng)前狀態(tài)i向這新狀態(tài)j的轉(zhuǎn)換接收概率，Δ=f（j）-f（i）表示狀態(tài)間能級(jí)的差值，當(dāng)能級(jí)增量Δ≤0時(shí)，接收新狀態(tài)，否則以某一概率接收新狀態(tài)。

3）判斷當(dāng)前溫度是否足夠低，當(dāng)溫度不夠低時(shí)，繼續(xù)進(jìn)行模擬退火操作；當(dāng)溫度足夠低，停止模擬退火操作，并記錄目前最佳效用函數(shù)值及最佳用戶，將最佳用戶作為下一次種群更新的目標(biāo)，繼續(xù)（8）；

8、判斷遺傳操作是否達(dá)到最大進(jìn)化代數(shù)maxgen，若沒(méi)有達(dá)到，繼續(xù)（6）-（7）；若達(dá)到，算法結(jié)束。此時(shí)搜索到的最優(yōu)解作為QGSA算法對(duì)所有用戶進(jìn)行的頻譜分配達(dá)到的納什均衡狀態(tài)。

三、算法仿真及比較分析

基于QGSA的頻譜分配仿真參數(shù)設(shè)定如下：

量子遺傳操作的種群規(guī)模pop=60，帶內(nèi)噪聲功率N=0.001，信道增益，每個(gè)用戶發(fā)射功率的最大值Pmax=1W、染色體編碼長(zhǎng)度length=20，進(jìn)化代數(shù)maxgen=300，量子變異概率pm=0.15，轉(zhuǎn)角步長(zhǎng)Δθ=0.08π；模擬退火操作時(shí)，初始溫度T=1000，退火系數(shù)λ=0.9，每一固定溫度下的迭代次數(shù)為L(zhǎng)=15，每一固定溫度下適應(yīng)度函數(shù)值允許最大連續(xù)未改進(jìn)次數(shù)cnt=3，退火算法運(yùn)行過(guò)程中更新解的概率Prenew=0.3，學(xué)習(xí)步長(zhǎng)step=0.2，搜索半徑sR=0.1。

以上仿真結(jié)果顯示：

QGSA算法在解決該優(yōu)化問(wèn)題時(shí)的尋優(yōu)性能優(yōu)于QGA算法，QGSA算法能夠在較短的時(shí)間內(nèi)達(dá)到更好的納什均衡狀態(tài)，這主要是因?yàn)镾A算法的引入使得QGSA算法能夠跳出局部最優(yōu)解，這恰恰克服了QGA“早熟收斂”的尋優(yōu)瓶頸，增強(qiáng)了QGSA的尋優(yōu)能力，使得QGSA表現(xiàn)出不錯(cuò)的尋優(yōu)能力，更能有效的解決頻譜分配問(wèn)題。

1、統(tǒng)計(jì)分析

在設(shè)定QGA和QGSA頻譜分配算法各自運(yùn)行30次，根據(jù)得到的實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果數(shù)據(jù)，從信道數(shù)量和用戶數(shù)量對(duì)頻譜分配的影響兩方面來(lái)進(jìn)行分析：

1）信道數(shù)量對(duì)頻譜分配結(jié)果的影響。在相同用戶數(shù)量情況下，隨著信道數(shù)量的增加，頻譜分配的總收益均呈現(xiàn)增大的趨勢(shì)，這主要是因?yàn)轭l譜的利用率得到了提升，從而使得整體的信道容量和增加。另外，隨著信道數(shù)量的增加，QGA和QGSA頻譜分配算法的頻譜分配性能的差距越來(lái)越大，QGSA的頻譜分配性能越來(lái)越好，這說(shuō)明在多信道的情況下，QGSA頻譜分配算法的優(yōu)勢(shì)越明顯。

2）用戶數(shù)量對(duì)頻譜分配結(jié)果的影響。在相同信道數(shù)量情況下，隨著用戶數(shù)量的增加，頻譜分配的總收益均呈現(xiàn)下降的趨勢(shì)，這主要是因?yàn)橛脩糁g的非合作博弈造成對(duì)頻譜資源的競(jìng)爭(zhēng)越發(fā)激烈，導(dǎo)致頻譜利用率下降，整體的總收益也出現(xiàn)下降趨勢(shì)。但是，總收益也不會(huì)一直遞減，從仿真數(shù)據(jù)來(lái)看，隨著用戶數(shù)量的繼續(xù)增加，總收益的下降趨勢(shì)趨于平穩(wěn)。并且，整個(gè)的頻譜分配結(jié)果表明，相比于QGA頻譜分配算法，QGSA頻譜分配算法受用戶數(shù)量的影響比較小，整體體現(xiàn)出更好的頻譜分配性能。

四、結(jié)論

本文在探討兩用戶和多用戶的認(rèn)知無(wú)線電頻譜分配問(wèn)題的非合作博弈數(shù)學(xué)模型基礎(chǔ)上，通過(guò)分析頻譜分配問(wèn)題的本質(zhì)，提出將具有更強(qiáng)搜索能力的量子遺傳模擬退火算法應(yīng)用于求解該問(wèn)題，并給出了基于QGSA的頻譜分配流程，通過(guò)仿真實(shí)驗(yàn)，將基于QGSA的頻譜分配性能與基于QGA的頻譜分配性能進(jìn)行了比對(duì)，驗(yàn)證了基于QGSA的頻譜分配性能的有效性。另外，根據(jù)仿真數(shù)據(jù)，從用戶數(shù)量和信道數(shù)量對(duì)頻譜分配性能的影響兩個(gè)方面分別進(jìn)行了總結(jié)分析。

參 考 文 獻(xiàn)

[1]謝顯中. 認(rèn)知無(wú)線電技術(shù)及其應(yīng)用[M]. 北京：電子工業(yè)出版 社， 2008.

[2] Mitola III J， Maguire Jr G Q. Cognitive radio： making software radios more personal[J]. Personal Communications， IEEE， 1999， 6（4）： 13-18.

[3] Haykin S. Cognitive radio： bra in-empowered wireless communications[J]. Selected Areas in Communications， IEEE Journal on， 2005， 23（2）： 201-220.

[4]曾軻， 李少謙. 基于博弈論的認(rèn)知無(wú)線電頻譜分配技術(shù)研究 [D][D]. 成都： 電子科技大學(xué)， 2007.

[5]張森. 基于博弈認(rèn)知無(wú)線網(wǎng)絡(luò)動(dòng)態(tài)頻譜分配和功率控制研究[D]. 北京郵電大學(xué)， 2010.

[6]楊蕊. 認(rèn)知無(wú)線電頻譜資源分配與共享技術(shù)研究[D]. 哈爾濱工程大學(xué)， 2012.

[7] L. Lu， X. Zhou， U. Onunkwo， an d G. Y. Li， “Ten years of research in spectrum sensing and sharing in cognitive radio，”EURASIP J. Wireless Commun. Netw.vol. 28， Jan. 2012 [Online]. Available： http：//jwcn.eurasipjournals.com/content/2012/1/28， [Online]. Available：

[8] Ding L， Melodia T， Batalama S N， et al. Distributed resource allocation in cognitive and cooperative ad hoc networks through joint routing， relay selection and spectrum allocation[J]. Computer Networks， 2015.

[9] Lu L， He D， Yu X， et al. Graph-based robust resource allocation for cognitive radio networks[C]//Acoustics， Speech and Signal Processing （ICASSP）， 2014 IEEE International Conference on. IEEE， 2014： 7298-7302.

[10] Aslam S， Shahid A， Lee K G. Primary user behavior aware spectrum allocation scheme for cognitive radio networks[J]. Computers & Electrical Engineering， 2015， 42： 135-147.

[11]趙知?jiǎng)牛?彭振， 鄭仕鏈， 等. 基于量子遺傳算法的認(rèn)知無(wú)線 電頻譜分配[J]. 物理學(xué)報(bào)， 2009， 58（2）： 1358-1363.

[12]朱東坡， 李飛. 量子遺傳算法在認(rèn)知無(wú)線電頻譜分配中的應(yīng)用[ J]. 2010 年通信理論與信號(hào)處理學(xué)術(shù)年會(huì)論文集， 2010.

[13]丁穎. 量子粒子群算法的改進(jìn)及其在認(rèn)知無(wú)線電頻譜分配中的應(yīng)用[D].南京郵電大學(xué)，2013.

[14]肖嬋嬋. 認(rèn)知無(wú)線電網(wǎng)絡(luò)場(chǎng)景下的主用戶定位方法研究[D].南 京郵電大學(xué)，2014.

[15]李士勇， 李盼池. 量子計(jì)算與量子優(yōu)化算法[M]. 哈爾濱： 哈爾濱工業(yè)大學(xué)出版社， 2009.