吳 軒，孫文勝，陸家明

(杭州電子科技大學 通信工程學院，浙江 杭州 310018)

基于遺傳蟻群優(yōu)化算法的認知無線電頻譜分配*

吳 軒，孫文勝，陸家明

(杭州電子科技大學 通信工程學院，浙江 杭州 310018)

針對認知無線電中的頻譜分配問題，提出一種融合了遺傳算法和蟻群算法優(yōu)點的頻譜分配方法。該方法利用遺傳算法快速隨機的群體性全局搜索能力生成初始解，然后利用銜接策略將遺傳算法初始解轉化為蟻群算法所需的信息素初始分布，最后利用蟻群算法正反饋、收斂高效的特點求取最優(yōu)解。通過仿真比較了該方法與顏色敏感圖著色算法的性能。結果表明動態(tài)融合了遺傳算法和蟻群算法的優(yōu)化算法性能明顯優(yōu)于顏色敏感圖著色算法，它能更好地實現網絡效益最大化。

認知無線電；頻譜分配；遺傳算法；蟻群算法；信息素

0 引 言

在認知無線電(Cognitive Radio,CR)的關鍵技術中，如何合理有效地實現頻譜分配是認知無線電的重點和難點問題[1]。頻譜的分配政策不僅要避免認知用戶對授權用戶的干擾和認知用戶之間的自干擾，還要滿足不同用戶對頻譜資源需求的多樣性，以期實現高可靠性的通信并最大化頻譜利用率[2]。因此，選擇一種高效的頻譜分配算法顯得尤為重要。

目前，遺傳算法與蟻群算法已廣泛應用于頻譜分配問題，而將二者結合的算法也不斷涌現。文獻[7]將遺傳算法與蟻群算法融合后求解一般性優(yōu)化問題，但該方法固定了遺傳算法迭代次數，不易在最佳融合時機銜接。文獻[8]將蟻群算法與遺傳算法不斷交叉，利用蟻群算法持續(xù)生成種群個體，但此方法種群進化所需迭代次數過多，效率較低。

本文提出遺傳蟻群優(yōu)化算法(Genetic Ant Colony Optimization,GACO)，對遺傳算法和蟻群算法分別進行優(yōu)化以提升效率，并制定銜接策略，使二者能在最佳時機融合。

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

設認知無線電系統(tǒng)中有m個可用頻譜信道，n個認知用戶。將可用頻譜信道依次標號為1～m，將認知用戶依次標號為1～n。認知無線電頻譜分配模型可由空閑頻譜矩陣、頻譜效益矩陣、干擾矩陣、無干擾頻譜分配矩陣和系統(tǒng)效益來描述[2-4]。

(1)空閑頻譜矩陣：當授權用戶使用其授權頻譜時，認知用戶無法使用該段頻譜。故空閑頻譜即在某個時間內，授權用戶未使用的頻譜。空閑頻譜矩陣為：

(1)

L是一個二元矩陣，用來表示頻譜是否為空閑頻譜。當ln,m=1時，表示認知用戶n可以使用頻譜m；當ln,m=0時，則表示認知用戶n不可以使用頻譜m。

(2)頻譜效益矩陣：

(2)

B是一個二元矩陣，表示各認知用戶使用各頻譜所得效益；bn,m表示認知用戶n在頻譜m上所得最大效益。

(3)干擾矩陣：

(3)

C用來判斷各認知用戶之間是否產生自干擾。當cn,k,m=1時，認知用戶n和k同時使用頻譜m時會產生自干擾。反之，當cn,k,m=0時則不會產生自干擾。

干擾矩陣只由空閑頻譜矩陣決定。當n=k時，cn,k,m=1-ln,m。

(4)無干擾頻譜分配矩陣：

(4)

A表示系統(tǒng)一次無干擾頻譜分配。當an,m=1時表示認知用戶n可在無干擾情形下使用頻譜m。無干擾分配矩陣必須滿足如下無干擾約束條件：

an,m×ak,m=0,ifcn,k,m=1,?n,k

(5)用戶效益矩陣：

(5)

R表示在無干擾分配情形下，認知用戶n獲得的真實效益。

(6)最優(yōu)效益函數：

①最大化網絡總效益MSR(Max-average Sum Reward，MSR)，其目標是使網絡系統(tǒng)的總效益最大，用公式可表示為：

(6)

則平均最大化網絡總效益MSRM(MSR-Mean)可表示為：

(7)

②最大比例公平性度量MPF(Max-Proportional-Fair)。它考慮了每個用戶的公平性，用公式可表示為：

(8)

2 遺傳蟻群優(yōu)化算法

2.1 GACO算法設計思想及總體框架

GACO算法基本設計思想是汲取遺傳算法和蟻群算法各自的優(yōu)點，克服遺傳算法對于系統(tǒng)中反饋信息利用不夠，求精確解效率低以及蟻群算法初期信息素匱乏，求解速度慢的缺點，使二者優(yōu)勢互補。

對于GACO算法中的遺傳算法部分，在其交叉、變異等操作的設計中，盡量涵蓋各種變化，使種群多樣性得以呈現，同時設置終止條件，生成GACO算法所需初始解，為其向蟻群算法的過渡做準備。而在蟻群算法部分，經銜接策略轉化過后生成的初始信息素分布能極大地提高其時間效率。算法總體框架如圖1所示。

圖1 GACO算法總體框架

2.2 遺傳算法部分

(1)基因編碼。將認知用戶依次編號為：1,2,3,…,n。根據L矩陣將每個認知用戶的可用頻譜篩選出來，對認知用戶進行逐一分配。如認知用戶1使用頻譜B，則標記為1B，認知用戶2使用頻譜C，則標記為2C。某一條染色體可表示為：1B,2C,…,NA。在進行進化率比較時，要將頻譜表示為二進制形式，如：10010,20011,…,N0001。

(2)初始種群產生。各認知用戶隨機選擇頻譜，組成染色體，但染色體必須符合干擾標準。在染色體中，根據基因的效益，將基因等分為若干組。然后再在各組內隨機產生基因排列順序，最后按效益從高到低的次序將這些組進行排序。依此產生初始種群中的各條染色體。根據經驗值，種群規(guī)模取50。

(3)適應度函數。適應度函數選定為平均最大化網絡效益總和：

(4)染色體的選擇。使用輪盤賭選擇法進行選擇。

(5)染色體的交叉。交叉是遺傳算法的一個關鍵步驟。本文的交叉方法為：在染色體中隨機選擇[1,n]之間一個整數為交叉點。在交叉點之前的基因片段不動，對交叉點之后的基因片段進行交叉操作。去除兩條染色體交叉點之前的基因片段中相同的基因(基因中認知用戶部分相同即為相同基因)，將各自的剩余基因分別存入數組x[] 和y[]中。將兩條染色體中交叉點后的基因片段分別與x[]和y[]比較，對與數組中元素不同的基因直接進行交換。對與數組中元素相同的基因，則先替換為相應數組中的元素再進行交換。設定一個交叉概率Pc，小于該概率時進行交叉。根據經驗值Pc取0.6。

(7)算法終止條件。遺傳算法的終止條件本質上即對于它與蟻群算法二者之間的最佳融合時機的判斷。設置最小遺傳迭代次數Genemin，最大遺傳迭代次數Genemax，最小進化率Genemin-improv-ratio，最小進化率連續(xù)代數為Genedie。當滿足以下條件之一，遺傳算法終止：①遺傳算法迭代次數達到Genemax；②迭代中連續(xù)Genedie代，子代優(yōu)化解改進率都小于Genemin-improv-ratio。

2.3 蟻群算法部分

(9)

(10)

式中Q為調整系數，bij為效益系數。

(2)授權用戶節(jié)點選擇策略。螞蟻按下式選擇授權用戶節(jié)點j。

(11)

(12)

式中，I為螞蟻可能訪問的節(jié)點的集合，其中不包含禁忌表中的元素。

(3)設置蟻群算法控制參數：α=β=1，信息素揮發(fā)率ρ=0.2，調整系數Q=10。

(4)螞蟻數的設置：為認知用戶節(jié)點數n。

(5)蟻群算法結束條件(滿足其一即可)：①螞蟻算法迭代次數達到Antmax；②迭代中連續(xù)Antdie代，子代優(yōu)化解改進率都小于Antmin-improv-ratio.

2.4 銜接策略部分

(1)設置兩種算法的動態(tài)融合時機：即遺傳算法的終止條件。

(2)設置蟻群算法所需信息素初始分布：將各邊eij的信息素初始分布設定為：

(13)

式中，τ0是邊eij上的信息素常數。Δτij是從遺傳算法所得解轉化而來的邊eij上的信息素增量。本文設置τ0=60。

(3)遺傳算法所得解轉化為信息素增量：將遺傳算法求解結果中適應度最好的前10%的解記為S10%。開始時，設置Δτij為0，如果邊eij被S10%中的某個解s歷經，則Δτij自加20。

3 仿真及結果分析

對于上述頻譜分配模型，研究人員主要采用顏色敏感圖著色(Color Sensitive Graph Coloring,CSGC)算法來解決[6-10]。本文利用MATLAB仿真對GACO算法和CSGC算法性能進行了比較。GACO算法參數設置如下:Genemin=15，Genemax=30，Genemin-improv-ratio=10%，Genedie=3，Antmax=100，Antdie=3，Antmin-improv-ratio=5%。

圖2和圖3分別展示了當認知用戶數N=20，可用頻譜數M=25時，在不同初始條件下，以最大化網絡總效益和最大比例公平性度量為目標函數的仿真結果。不同實驗中B，L，C不同，同一次實驗中CSGC算法和GACO算法所采用的B，L，C相同，B，L，C根據文獻[5]附錄I提供的偽碼仿真生成。

從圖2中網絡總效益方面來看，基于GACO算法的頻譜分配明顯優(yōu)于基于CSGC算法的頻譜分配。而依據圖3可知基于GACO算法的頻譜分配公平性也比基于CSGC算法的頻譜分配更高、更穩(wěn)定。

圖2 GACO和CSGC的網絡總效益比較

圖3 GACO和CSGC的公平性比較

圖4給出了可用頻譜數M=30時平均效益隨認知用戶數N的變化曲線。由圖知，基于GACO算法的頻譜分配所得到的平均效益均大于CSGC算法獲得的平均效益。

圖4 N變化時的算法性能

圖5給出了認知用戶數N=20時平均效益隨可用頻譜數M的變化曲線。由圖知，基于GACO算法的頻譜分配所得到的平均效益均大于CSGC算法獲得的平均效益。

圖5 M變化時的算法性能

4 結 語

合理有效地分配認知用戶所需的頻譜是認知無線網絡提供可靠通信服務的關鍵。認知無線電頻譜分配問題可以看做一個優(yōu)化問題。將遺傳算法或蟻群算法單獨應用于該優(yōu)化問題已有先例。本文汲二者之所長，使用GACO算法來求解該優(yōu)化問題，并與顏色敏感圖著色算法進行了性能比較。仿真結果表明基于GACO算法的認知無線電頻譜分配方法能更好地提升網絡效益、增加頻譜分配的公平性。仿真過程中，一些初始值的設定，均采用了經驗值，如何更好地優(yōu)化這些初值將是本文深入探究的一個關鍵問題。

[1] 楊淼，安建平.認知無線網絡中一種基于蟻群優(yōu)化的頻譜分配算法[J].電子與信息學報，2011,33(10):2306-2311. YANG Miao, An Jian-ping. An Ant Colony Optimization Alogorithm for Spectrum Allocation in Cognitive Radio Networks[J]. Journal of Electronics & Information Technology, 2011, 33(10): 2306-2311.

[2] 趙知勁，彭振，鄭仕鏈等.基于量子遺傳算法的認知無線電頻譜分配[J].物理學報，2009，58(02):1358-1363. ZHAO Zhi-jin, PENG Zhen, ZHENG Shi-lian. Cognitive Radio Spectrum Allocation based on Quantum Genetic Algorithm[J]. Acta Physica Sinica,2009, 58(02): 1358-1363.

[3] 彭振，趙知勁，鄭仕鏈.基于混合蛙跳算法的認知無線電頻譜分配[J].計算機工程,2010,36(03):210-217.

PENG Zhen, ZHAO Zhi-jin, ZHENG Shi-lian, Cognitive Radio Spectrum Allocation based on Shuffled Frog Leaping Algorithm[J]. Computer Engineering, 2010, 36(03):210-217.

[4] Schwarz H, Marpe D, Wiegand T. Overview of the Scalable Video Coding of the H.264/AVC Standard [J]. IEEE Trans. On Circuits and Systems for Video Technology, 2007, 17(9): 1103-1120.

[5] 肖冬榮，楊磊. 基于遺傳算法的關聯規(guī)則數據挖掘[J]. 通信技術， 2010, 43(01):205-207. XIAO Dong-rong, YANG Lei. Association Rule Data Mining based on Genetic Algorithm[J]. Communications Technology, 2010, 43(01):205-207.

[6] PENG C, ZHENG H, ZHAO B Y. Utilization and Fariness in Spectrum Allocation for Opportunistic Spectrum Access [J]. Mobile Networks and Applications, 2006, 11:555-576.

[7] DING Jian-li, CHEN Zeng-qiang, YUAN Zhu-zhi. On the Combination of Genetic Algorithm [J]. Journal of Computer Research and Development, 2003, 40(9):1351-1356.

[8] LI Zhi, XU Chuan-pei, MO Wei. Initialization for Synchronous Sequential Circuits based on Ant Algorithm & Genetic Algorithm. Acta Electronica Sinica, 2003,31(8):1276-1280.

[9] XIONG Z H, LI S S, CHEN J H. Hardware/Software Partitioning based on Dynamic Combination of Genetic Algorithm and Ant Algorithm [J]. Journal of Software, 2005, 16(4): 503-512(in Chinese with English Abstract).

[10] 何利，鄭湘渝，劉振坤.基于圖著色理論的最大效用頻譜分配算法[J].計算機工程，2011, 37(19):93-95. HE Li, ZHENG Xiang-yu, LIU Zhen-kun. Maximum Utility Spectrum Allocation Algorithm based on Graph Coloring Theory[J]. Computer Engineering, 2011, 37(19):93-95.

Cognitive Radio Spectrum Allocation based on Genetic Ant Colony Optimization

WU Xuan，SUN Wen-sheng，LU Jia-ming

(College of Communication Engineering, Hangzhou Dianzi University, Hangzhou Zhejiang 310018,China)

In light of spectrum allocation in cognitive radio network, a spectrum allocation method combining the merits of genetic algorithm and ant colony algorithm is proposed in which the fast and stochastic global search in group is adopted to generate initial solution.And then, transitive strategy is used to convert initial solution of genetic algorithm to the required initial pheromone distribution of ant colony algorithm. Finally, the optimal solution is acquired by ant colony algorithm with characteristics of positive feedback and efficient convergence. The performance of the proposed method is compared with that of the color sensitive graph coloring algorithm by simulation,and the results show that the optimization algorithm in dynamical combination of genetic algorithm and ant colony algorithm enjoys remarkable superiority as compared with the color sensitive graph coloring algorithm, and could fairly maximize the network benefit.

cognitive radio; spectrum allocation; genetic algorithm; ant colony algorithm; pheromone

10.3969/j.issn.1002-0802.2015.11.012

2015-06-01；

2015-09-30 Received date:2015-06-01；Revised date：2015-09-30

TN911.7

A

1002-0802(2015)11-1265-05

吳 軒(1990—)，男，碩士研究生，主要研究方向為多媒體通信與無線通信；

孫文勝(1966—)，男，副教授，主要研究方向為多媒體通信與無線通信；

陸家明(1990—)，男，碩士研究生，主要研究方向為無線通信技術。