劉蕊蕊

(山東科技大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，山東 青島 266590)

基于多目標(biāo)混合遺傳算法認(rèn)知無線電頻譜分配

劉蕊蕊

(山東科技大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，山東 青島 266590)

在認(rèn)知無線電的頻譜分配問題中，論文提出基于圖著色模型的多目標(biāo)混合遺傳算法。該算法采用多目標(biāo)函數(shù)為適應(yīng)度函數(shù)，將模擬退火算法嵌入到遺傳算法的循環(huán)中，彌補(bǔ)遺傳算法局部搜索能力的不足。仿真結(jié)果表明多目標(biāo)混合遺傳算法能增強(qiáng)全局搜索能力，提高收斂速度，更好地實(shí)現(xiàn)系統(tǒng)效益最大化。

認(rèn)知無線電；頻譜分配；多目標(biāo)混合遺傳算法；模擬退火算法

隨著遠(yuǎn)程通信產(chǎn)業(yè)的迅速發(fā)展，無線電頻譜的需求急速上升。再加上現(xiàn)有頻譜資源利用率不到10%， 導(dǎo)致頻譜資源越來越稀缺。[1]為解決這一問題，認(rèn)知無線電(CR)的概念[2]被Joseph Mitola 博士首先提出。(CR)是一種能感知周圍環(huán)境的智能無線電系統(tǒng)，并可以使用智能的學(xué)習(xí)方法，與周圍環(huán)境進(jìn)行信息交流。因此，本地頻譜可以被認(rèn)知用戶自適應(yīng)占用，同時(shí)在通信過程中不會(huì)給主用戶帶來不利干擾，實(shí)現(xiàn)頻譜共享，[3]大大提高頻譜利用率。

認(rèn)知無線電頻譜分配現(xiàn)已成為研究熱點(diǎn)。文獻(xiàn)[4]應(yīng)用量子遺傳算法解決頻譜分配問題。文獻(xiàn)[5]將遺傳算法(Genetic Algorithm， GA)應(yīng)用到譜分配領(lǐng)域，驗(yàn)證了(GA)在此領(lǐng)域的有效性。文獻(xiàn)[6]認(rèn)為遺傳算法雖然在網(wǎng)絡(luò)效益上高于經(jīng)典算法，但容易陷入局部最優(yōu)解。文獻(xiàn)[7]提出基于遺傳算法的MOP 算法(Max-Overall-Performance Algorithm， MOPA)，通過改變適應(yīng)度函數(shù)來提高系統(tǒng)效益。文獻(xiàn)[8]和文獻(xiàn)[9]提出以進(jìn)化博弈論模型為基礎(chǔ)的頻譜分配。其它頻譜分配問題的數(shù)學(xué)模型有圖著色模型，[10-11]拍賣競價(jià)模型等。[12-13]

本文針對(duì)靜態(tài)系統(tǒng)給出解決方案。首先，建立基于圖著色模型的認(rèn)知無線電頻譜分配方法，然后采用多目標(biāo)遺傳算法優(yōu)化給出問題的求解方法。為保證遺傳算法的全局搜索性， 并避免遺傳算法陷入局部最優(yōu)解，我們?cè)谶z傳算法過程中引入模擬退火算法。

本文結(jié)構(gòu)如下: 首先定義認(rèn)知無線電頻譜分配模型相關(guān)的模型矩陣；然后給出多目標(biāo)混合遺傳算法的適應(yīng)度函數(shù)，遺傳算子。借助MATLAB 仿真工具，文章最后給出了靜態(tài)系統(tǒng)的仿真結(jié)果，并與其它方法進(jìn)行比較，說明了本文算法的有效性。

1 認(rèn)知無線電頻譜分配模型

論文采用信道可用性矩陣，信道獎(jiǎng)勵(lì)矩陣，干擾限制矩陣，免沖突信道分配矩陣來描述圖著色模型。假設(shè)系統(tǒng)內(nèi)有n個(gè)認(rèn)知用戶，m條信道。各個(gè)矩陣定義如下:

定義1 信道可用性矩陣

L={lij|lijε∈{0,1}}n×m

表示認(rèn)知用戶i(1≤i≤n)是否可以使用信道j(1≤j≤m)。若可以使用，則lij=1；否則lij=0。

定義2 信道獎(jiǎng)勵(lì)矩陣

B={bij|bij>{0,1}}n×m

其中bij代表i(1≤i≤n)使用信道j(1≤j≤m)所獲得的獎(jiǎng)勵(lì)。

定義3 干擾限制矩陣

C={cikj|cikj∈{0,1}}n×n×m

表示網(wǎng)絡(luò)中的干擾。當(dāng)i=k時(shí)，ciij表示授權(quán)用戶與認(rèn)知用戶之間的干擾，若認(rèn)知用戶i使用頻譜j時(shí)對(duì)同時(shí)使用該頻譜的授權(quán)用戶產(chǎn)生干擾，則ciij=1，反之ciij=0；當(dāng)i≠k時(shí)，表示認(rèn)知用戶之間的干擾，若認(rèn)知用戶i與k同時(shí)使用頻譜j，就會(huì)產(chǎn)生干擾，則cikj=1，反之cikj=0。

定義4 免沖突信道分配矩陣

A={aij|aij∈{0,1},aij}≤lij}n×m

當(dāng)aij=1時(shí)表示頻譜j分配給了認(rèn)知用戶i，反之a(chǎn)ij=0。同時(shí)，分配矩陣A必須滿足干擾矩陣C的約束：

cikj=1,?1≤j≤m; 1≤i, k≤n, i≠k?aij·akj=0

2 多目標(biāo)混合遺傳算法設(shè)計(jì)

2.1 染色體編碼。

論文采用二進(jìn)制編碼方法對(duì)染色體進(jìn)行編碼。當(dāng)可用性矩陣L中的元素等0時(shí)，分配矩陣A所對(duì)應(yīng)的元素必為0。為了減少運(yùn)算，提高運(yùn)行效率，僅對(duì)lij=1的位置編碼，故矩陣L中元素為1的個(gè)數(shù)決定染色體編碼之后二進(jìn)制串的長度。染色體的編解碼示例如圖1所示: 假設(shè)有四個(gè)用戶，五條信道，Xi代表第i條染色體，xij∈[0,1], j=(1,2,3,4,5,6,7)。

圖1 染色體編解碼示例

原始群體中每個(gè)染色體的二進(jìn)制編碼都是隨機(jī)形成的并且容易受到交叉和突變的影響， 因此它并不完全滿足預(yù)先定義的干擾矩陣C，故提出以下方法進(jìn)行改進(jìn):

對(duì)于所有的頻譜j(1≤j≤m)，觀察所有的數(shù)對(duì)(i,k)是否滿足cikj=1；若cikj=1，檢查aij與akj是否同時(shí)為1，如果同時(shí)為1，則隨機(jī)選取一個(gè)為0。

2.2 適應(yīng)度函數(shù)。

在論文中， 我們考慮以下目標(biāo)函數(shù):

系統(tǒng)總效益函數(shù)

最大比例公平函數(shù)

其中Ai(i=1,2,3,…,n)為A的第I行元素。

本文采用多目標(biāo)函數(shù)的權(quán)重方法獲得遺傳算法的總適應(yīng)度函數(shù)。可以隨機(jī)調(diào)整系統(tǒng)效益和最大比例公平的權(quán)重值，若認(rèn)知用戶間的頻譜分配著重于最大比例公平，則將最大比例公平函數(shù)U的權(quán)重設(shè)的大些，反之亦然。設(shè)R的權(quán)重為α，U(A)fair的權(quán)重為β(α+β=1)，則總目標(biāo)函數(shù)為

f(A)=α·R(A)+β·U(A)fair

2.3 選擇，交叉，變異操作。

本文采用“輪盤賭”選擇法。在該方法中，每個(gè)個(gè)體的選擇概率與它的適應(yīng)度值成比例。設(shè)群體大小為n，其中個(gè)體Xk的適應(yīng)度為fk(A)，則Xk被選擇的概率

選擇個(gè)體后，隨機(jī)組成交配對(duì)，為后面的交叉操作創(chuàng)造條件。

交叉操作采用兩點(diǎn)交叉，即在個(gè)體中隨機(jī)設(shè)定兩個(gè)交叉點(diǎn)，然后將兩交叉點(diǎn)之間個(gè)體結(jié)構(gòu)互換。自適應(yīng)交叉概率

自適應(yīng)變異概率

2.4 模擬退火操作。

模擬退火算法 (Simulated Annealing，SA) 以通過選擇，交叉，變異等操作產(chǎn)生的種群為當(dāng)前解，在鄰域內(nèi)進(jìn)行局部搜索，產(chǎn)生優(yōu)化的新種群。并進(jìn)入到下一個(gè)遺傳算法的進(jìn)化循環(huán)中。為了更好地實(shí)現(xiàn)本文算法對(duì)頻譜的分配，SA直接操作GA生成種群的染色體，設(shè)GA 的進(jìn)化代數(shù)g為SA的退火時(shí)間，GA 的適應(yīng)度函數(shù)看作SA的能量函數(shù)。

模擬退火操作具體過程如下:

(1) 新染色體產(chǎn)生方式。

當(dāng)前解Xk解碼為免沖突信道分配矩陣A，隨機(jī)生成一個(gè)擾動(dòng)量W(長度和認(rèn)知用戶的個(gè)數(shù)相等)，隨機(jī)替換A的某個(gè)信道對(duì)其進(jìn)行約束操作，形成新的分配矩陣A，將A映射為新生的染色體Xj。

(2) 溫度更新函數(shù)。

為了計(jì)算簡便，采用時(shí)齊的方式進(jìn)行溫度管理，即：

T(g)=K·T(g-1)

K為Boltzmann常數(shù)，其中T(g)為當(dāng)前退火溫度。

(3) 新染色體接受準(zhǔn)則。

因本文所求的是極大值，故新解的接受率如以下函數(shù)所示：

fk(A)，fj(A)分別為染色體Xk與Xj的適應(yīng)度。

3 多目標(biāo)混合遺傳算法流程

設(shè)最大遺傳代數(shù)G=500為終止條件，多目標(biāo)混合遺傳算法流程如下：

(2)種群初始化。隨機(jī)選取n個(gè)初始個(gè)體組成原始群體Q(g)，令進(jìn)化代數(shù)g=0并對(duì)染色體進(jìn)行二進(jìn)制編碼，得到二進(jìn)制串X,X2,X3,…XN。

(3)將染色體Xi(i=1,2,3,…,Xn)的第s個(gè)字節(jié)映射到aij，其中(i,j)是L1中的第s個(gè)元素，并且1≤s≤d。對(duì)于任意的j，觀察所有的數(shù)對(duì)(i,k)是否滿足cikj=1；若cikj=1，核查一下aij與akj是否同時(shí)等于1。若同時(shí)為1，則隨機(jī)選取一個(gè)為0，令一個(gè)保持不變。

(4)根據(jù)權(quán)重值計(jì)算適應(yīng)度函數(shù)值。

(5)對(duì)Q(g)執(zhí)行選擇、交叉、變異操作。得到新種群Q1(g)。

(6)對(duì)種群Q2(g)中所有染色體進(jìn)行模擬退火操作。得到新的群體Q3(g)。

(7)終止條件判斷。若g≤G(最大遺傳代數(shù))，則g=g+1，將Q3(g)作為新的下一代群體，然后轉(zhuǎn)到混合算法的第二步；若g>G，則輸出結(jié)果，算法結(jié)束。

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

本文仿真是在Windows環(huán)境中利用MATLAB建立的。對(duì)本文算法和基于圖著色模型的多目標(biāo)遺傳算法和一般遺傳算法進(jìn)行比較。在仿真過程中參數(shù)設(shè)置如下:目標(biāo)函數(shù)權(quán)重值α=0.6，β=0.4，認(rèn)知用戶n=10，信道m(xù)=18。隨機(jī)生成L，B，C矩陣，L，C中的元素由0，1組成，B中元素為[0,n]中的自然數(shù)。

隨著迭代次數(shù)的增加，系統(tǒng)效益逐漸增加，本文算法迭代250次達(dá)到最優(yōu)解，其他兩種算法迭代400次左右達(dá)到最優(yōu)解，很明顯本文算法收斂速度較快，且系統(tǒng)效益更高，如圖2所示。

隨著認(rèn)知用戶的增加，系統(tǒng)效益逐漸減少，但在認(rèn)知用戶相同情況下，本文算法的系統(tǒng)效益明顯優(yōu)于其他兩種算法，如圖3所示。

圖4表示系統(tǒng)效益隨試驗(yàn)次數(shù)的變化曲線圖，本文算法的優(yōu)越性雖然在很少情況下效果不明顯，但在大部分情況下系統(tǒng)效益明顯優(yōu)于其他兩種算法。

圖5表示三種算法時(shí)間開銷隨迭代次數(shù)的變化曲線圖，由圖5可知:算法的時(shí)間開銷隨著迭代次數(shù)的增加逐漸上升，本文提出的算法分配時(shí)間開銷明顯比多目標(biāo)遺傳算法和一般遺傳算法的要少，故此算法提高了系統(tǒng)的運(yùn)行效率。

結(jié)束語

論文針對(duì)現(xiàn)有頻譜分配算法的不足，將多目標(biāo)混合遺傳算法應(yīng)用到頻譜分配中，提高了頻譜的利用率以及系統(tǒng)效益，同時(shí)還減少了系統(tǒng)的運(yùn)行時(shí)間，提高了收斂速度。通過仿真可以得出以下結(jié)論:該算法系統(tǒng)效益高，收斂速度快，優(yōu)化過程較簡單.故此方法為提高頻譜利用率，解決頻譜分配問題提供了新思路。

[1]Akella A，Judd G，Seshan S，Steenkiste P. Self-management in Chaotic Wireless Deployments[J]. International Conference on Mobile Computing and Networking，2005，13(6):737-755.

[2]Milola J. Making Cognitive Radio:Software Radios More Personal[J]. IEEE Personal Communications，1999，6(4):13-18.

[3]Akyildiz IF，Lee W，Vuran MC，Mohanty S.Next Generation Dynamic Spectrum Access Cognitive Radio Wireless Networks: A Survey[J].Computer Networks，2006，50(13):2127-2159.

[4] Zhao Zhijin，Peng Zhen，Zheng Shilian，et al. Cognitive Radio Spectrum Assignment Based on Quantum Genetic Algorithm[J]. Acta Physica Sinica，2009，58(2):1358-1363.

[5] Mustafa Y，Nainay E.Island Genetic Algorithm-based Cognitive Networks[D].Blacksburg，USA: Virginia Polytechnic Institute and State University，2009.

[6]Zhao Zhijin，Peng Zhen.Cognitive Radio Spectrum Allocation Using Evolutionary Algorithms[J]. IEEE Transactions on Wireless Communications，2009，8(9):4421-4425.

[7]Wen Kai，F(xiàn)u Lingsheng，Li Xuesong.Genetic Algorithm Based Spectrum Allocation for Cognitive Radio Networks[J]. Advances in Computer，Communication，Control & Automation，2012，693-700.

[8]Nie N，Comaniciu C. Adaptive Channel Allocation Spectrum Etiquette for Cognitive Radio Networks[J]. IEEE Computer Society，2005，11(6):269-278.

[9]Ni Qiufen，Zhu Rongbo，Wu Zhenguo，Sun Yongli.Game-based Spectrum Allocation Algorithm in Cognitive Radio Networks[J]. Springer Berlin Heidelberg，2013，1-13.

[10]Tandra R，Mishra SM，Sahai A. What Is a Spectrum Hole and What Does It Take to Recognize One[J]. Proceedings of the IEEE，2009，97(5):824-848.

[11]Chunyi Peng，Haitao Zheng. Utilization and Fairness in Spectrum Assignment for Opportunistic Spectrum Access[J]. Mobile Networks and Applications，2006，11(4):555-576.

[12]Huang J，Berry RA，Honig ML. Auction-based Spectrum Sharing[J].Mobile Networks and Applications，2006，11(3):405-408.

[13]Kloeck C，Jaekel H，Jondral FK. Dynamic and Local Combined Pricing，Allocation and Billing System with Cognitive Radios[J]. IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks 2005，73-81.

Class No.:TN92:O29 Document Mark：A

(責(zé)任編輯：宋瑞斌)

Allocation of Cognitive Radio Spectrum Based on Multi-objective Hybrid Genetic Algorithm

Liu Ruirui

(School of Mathematics and System Science, Shandong University of Science and Technology, Qingdao，Shandong 266590，China)

As for the cognitive radio spectrum allocation，this paper puts forward a multi-objective hybrid genetic algorithm based on graph coloring model. The algorithm adopts the multi-objective function as the fitness function, embedding the simulated annealing algorithm into the cycle of basic genetic algorithm in order to make up the lack of local search ability of genetic algorithm. Simulation results show that multi-objective hybrid genetic algorithm can enhance the global search ability and convergence speed，and can realize the system benefit maximization better.

cognitive radio; spectrum allocation; multi-objective hybrid genetic algorithm; simulated annealing algorithm

劉蕊蕊，在讀碩士，山東科技大學(xué)。研究方向：計(jì)算理論與數(shù)據(jù)處理。

1672-6758(2016)12-0059-4

TN92:O29

A