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

吳 軒，孫文勝，陸家明

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

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

吳 軒，孫文勝，陸家明

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

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

認(rèn)知無(wú)線電；頻譜分配；遺傳算法；蟻群算法；信息素

0 引 言

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

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

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

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

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

(1)空閑頻譜矩陣：當(dāng)授權(quán)用戶使用其授權(quán)頻譜時(shí)，認(rèn)知用戶無(wú)法使用該段頻譜。故空閑頻譜即在某個(gè)時(shí)間內(nèi)，授權(quán)用戶未使用的頻譜?？臻e頻譜矩陣為：

(1)

L是一個(gè)二元矩陣，用來(lái)表示頻譜是否為空閑頻譜。當(dāng)ln,m=1時(shí)，表示認(rèn)知用戶n可以使用頻譜m；當(dāng)ln,m=0時(shí)，則表示認(rèn)知用戶n不可以使用頻譜m。

(2)頻譜效益矩陣：

(2)

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

(3)干擾矩陣：

(3)

C用來(lái)判斷各認(rèn)知用戶之間是否產(chǎn)生自干擾。當(dāng)cn,k,m=1時(shí)，認(rèn)知用戶n和k同時(shí)使用頻譜m時(shí)會(huì)產(chǎn)生自干擾。反之，當(dāng)cn,k,m=0時(shí)則不會(huì)產(chǎn)生自干擾。

干擾矩陣只由空閑頻譜矩陣決定。當(dāng)n=k時(shí)，cn,k,m=1-ln,m。

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

(4)

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

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

(5)用戶效益矩陣：

(5)

R表示在無(wú)干擾分配情形下，認(rèn)知用戶n獲得的真實(shí)效益。

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

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

(6)

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

(7)

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

(8)

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

2.1 GACO算法設(shè)計(jì)思想及總體框架

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

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

圖1 GACO算法總體框架

2.2 遺傳算法部分

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

(2)初始種群產(chǎn)生。各認(rèn)知用戶隨機(jī)選擇頻譜，組成染色體，但染色體必須符合干擾標(biāo)準(zhǔn)。在染色體中，根據(jù)基因的效益，將基因等分為若干組。然后再在各組內(nèi)隨機(jī)產(chǎn)生基因排列順序，最后按效益從高到低的次序?qū)⑦@些組進(jìn)行排序。依此產(chǎn)生初始種群中的各條染色體。根據(jù)經(jīng)驗(yàn)值，種群規(guī)模取50。

(3)適應(yīng)度函數(shù)。適應(yīng)度函數(shù)選定為平均最大化網(wǎng)絡(luò)效益總和：

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

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

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

2.3 蟻群算法部分

(9)

(10)

式中Q為調(diào)整系數(shù)，bij為效益系數(shù)。

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

(11)

(12)

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

(3)設(shè)置蟻群算法控制參數(shù)：α=β=1，信息素?fù)]發(fā)率ρ=0.2，調(diào)整系數(shù)Q=10。

(4)螞蟻數(shù)的設(shè)置：為認(rèn)知用戶節(jié)點(diǎn)數(shù)n。

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

2.4 銜接策略部分

(1)設(shè)置兩種算法的動(dòng)態(tài)融合時(shí)機(jī)：即遺傳算法的終止條件。

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

(13)

式中，τ0是邊eij上的信息素常數(shù)。Δτij是從遺傳算法所得解轉(zhuǎn)化而來(lái)的邊eij上的信息素增量。本文設(shè)置τ0=60。

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

3 仿真及結(jié)果分析

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

圖2和圖3分別展示了當(dāng)認(rèn)知用戶數(shù)N=20，可用頻譜數(shù)M=25時(shí)，在不同初始條件下，以最大化網(wǎng)絡(luò)總效益和最大比例公平性度量為目標(biāo)函數(shù)的仿真結(jié)果。不同實(shí)驗(yàn)中B，L，C不同，同一次實(shí)驗(yàn)中CSGC算法和GACO算法所采用的B，L，C相同，B，L，C根據(jù)文獻(xiàn)[5]附錄I提供的偽碼仿真生成。

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

圖2 GACO和CSGC的網(wǎng)絡(luò)總效益比較

圖3 GACO和CSGC的公平性比較

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

圖4 N變化時(shí)的算法性能

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

圖5 M變化時(shí)的算法性能

4 結(jié) 語(yǔ)

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

[1] 楊淼，安建平.認(rèn)知無(wú)線網(wǎng)絡(luò)中一種基于蟻群優(yōu)化的頻譜分配算法[J].電子與信息學(xué)報(bào)，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] 趙知?jiǎng)牛碚?，鄭仕鏈?基于量子遺傳算法的認(rèn)知無(wú)線電頻譜分配[J].物理學(xué)報(bào)，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] 彭振，趙知?jiǎng)牛嵤随?基于混合蛙跳算法的認(rèn)知無(wú)線電頻譜分配[J].計(jì)算機(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ān)聯(lián)規(guī)則數(shù)據(jù)挖掘[J]. 通信技術(shù)， 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].計(jì)算機(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—)，男，碩士研究生，主要研究方向?yàn)槎嗝襟w通信與無(wú)線通信；

孫文勝(1966—)，男，副教授，主要研究方向?yàn)槎嗝襟w通信與無(wú)線通信；

陸家明(1990—)，男，碩士研究生，主要研究方向?yàn)闊o(wú)線通信技術(shù)。