基于多目標混合遺傳算法認知無線電頻譜分配

劉蕊蕊

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

基于多目標混合遺傳算法認知無線電頻譜分配

劉蕊蕊

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

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

認知無線電；頻譜分配；多目標混合遺傳算法；模擬退火算法

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

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

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

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

1 認知無線電頻譜分配模型

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

定義1 信道可用性矩陣

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

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

定義2 信道獎勵矩陣

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

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

定義3 干擾限制矩陣

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

表示網絡中的干擾。當i=k時，ciij表示授權用戶與認知用戶之間的干擾，若認知用戶i使用頻譜j時對同時使用該頻譜的授權用戶產生干擾，則ciij=1，反之ciij=0；當i≠k時，表示認知用戶之間的干擾，若認知用戶i與k同時使用頻譜j，就會產生干擾，則cikj=1，反之cikj=0。

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

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

當aij=1時表示頻譜j分配給了認知用戶i，反之aij=0。同時，分配矩陣A必須滿足干擾矩陣C的約束：

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

2 多目標混合遺傳算法設計

2.1 染色體編碼。

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

圖1 染色體編解碼示例

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

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

2.2 適應度函數。

在論文中， 我們考慮以下目標函數:

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

最大比例公平函數

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

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

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

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

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

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

交叉操作采用兩點交叉，即在個體中隨機設定兩個交叉點，然后將兩交叉點之間個體結構互換。自適應交叉概率

自適應變異概率

2.4 模擬退火操作。

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

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

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

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

(2) 溫度更新函數。

為了計算簡便，采用時齊的方式進行溫度管理，即：

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

K為Boltzmann常數，其中T(g)為當前退火溫度。

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

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

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

3 多目標混合遺傳算法流程

設最大遺傳代數G=500為終止條件，多目標混合遺傳算法流程如下：

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

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

(4)根據權重值計算適應度函數值。

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

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

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

4 仿真結果與分析

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

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

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

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

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

結束語

論文針對現(xiàn)有頻譜分配算法的不足，將多目標混合遺傳算法應用到頻譜分配中，提高了頻譜的利用率以及系統(tǒng)效益，同時還減少了系統(tǒng)的運行時間，提高了收斂速度。通過仿真可以得出以下結論:該算法系統(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

(責任編輯：宋瑞斌)

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

劉蕊蕊，在讀碩士，山東科技大學。研究方向：計算理論與數據處理。

1672-6758(2016)12-0059-4

TN92:O29

A