基于遗传蚁群优化算法的认知无线电频谱分配*

2015-03-25孙文胜陆家明

通信技术 2015年11期

关键词：遗传算法频谱染色体

吴轩，孙文胜，陆家明

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

基于遗传蚁群优化算法的认知无线电频谱分配*

吴轩，孙文胜，陆家明

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

针对认知无线电中的频谱分配问题，提出一种融合了遗传算法和蚁群算法优点的频谱分配方法。该方法利用遗传算法快速随机的群体性全局搜索能力生成初始解，然后利用衔接策略将遗传算法初始解转化为蚁群算法所需的信息素初始分布，最后利用蚁群算法正反馈、收敛高效的特点求取最优解。通过仿真比较了该方法与颜色敏感图着色算法的性能。结果表明动态融合了遗传算法和蚁群算法的优化算法性能明显优于颜色敏感图着色算法，它能更好地实现网络效益最大化。

认知无线电；频谱分配；遗传算法；蚁群算法；信息素

0 引言

在认知无线电(Cognitive Radio,CR)的关键技术中，如何合理有效地实现频谱分配是认知无线电的重点和难点问题[1]。频谱的分配政策不仅要避免认知用户对授权用户的干扰和认知用户之间的自干扰，还要满足不同用户对频谱资源需求的多样性，以期实现高可靠性的通信并最大化频谱利用率[2]。因此，选择一种高效的频谱分配算法显得尤为重要。

目前，遗传算法与蚁群算法已广泛应用于频谱分配问题，而将二者结合的算法也不断涌现。文献[7]将遗传算法与蚁群算法融合后求解一般性优化问题，但该方法固定了遗传算法迭代次数，不易在最佳融合时机衔接。文献[8]将蚁群算法与遗传算法不断交叉，利用蚁群算法持续生成种群个体，但此方法种群进化所需迭代次数过多，效率较低。

本文提出遗传蚁群优化算法(Genetic Ant Colony Optimization,GACO)，对遗传算法和蚁群算法分别进行优化以提升效率，并制定衔接策略，使二者能在最佳时机融合。

1 认知无线电频谱分配模型

设认知无线电系统中有m个可用频谱信道，n个认知用户。将可用频谱信道依次标号为1～m，将认知用户依次标号为1～n。认知无线电频谱分配模型可由空闲频谱矩阵、频谱效益矩阵、干扰矩阵、无干扰频谱分配矩阵和系统效益来描述[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表示系统一次无干扰频谱分配。当an,m=1时表示认知用户n可在无干扰情形下使用频谱m。无干扰分配矩阵必须满足如下无干扰约束条件：

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

(5)用户效益矩阵：

(5)

R表示在无干扰分配情形下，认知用户n获得的真实效益。

(6)最优效益函数：

①最大化网络总效益MSR(Max-average Sum Reward，MSR)，其目标是使网络系统的总效益最大，用公式可表示为：

(6)

则平均最大化网络总效益MSRM(MSR-Mean)可表示为：

(7)

②最大比例公平性度量MPF(Max-Proportional-Fair)。它考虑了每个用户的公平性，用公式可表示为：

(8)

2 遗传蚁群优化算法

2.1 GACO算法设计思想及总体框架

GACO算法基本设计思想是汲取遗传算法和蚁群算法各自的优点，克服遗传算法对于系统中反馈信息利用不够，求精确解效率低以及蚁群算法初期信息素匮乏，求解速度慢的缺点，使二者优势互补。

对于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)初始种群产生。各认知用户随机选择频谱，组成染色体，但染色体必须符合干扰标准。在染色体中，根据基因的效益，将基因等分为若干组。然后再在各组内随机产生基因排列顺序，最后按效益从高到低的次序将这些组进行排序。依此产生初始种群中的各条染色体。根据经验值，种群规模取50。

(3)适应度函数。适应度函数选定为平均最大化网络效益总和：

(4)染色体的选择。使用轮盘赌选择法进行选择。

(5)染色体的交叉。交叉是遗传算法的一个关键步骤。本文的交叉方法为：在染色体中随机选择[1,n]之间一个整数为交叉点。在交叉点之前的基因片段不动，对交叉点之后的基因片段进行交叉操作。去除两条染色体交叉点之前的基因片段中相同的基因(基因中认知用户部分相同即为相同基因)，将各自的剩余基因分别存入数组x[] 和y[]中。将两条染色体中交叉点后的基因片段分别与x[]和y[]比较，对与数组中元素不同的基因直接进行交换。对与数组中元素相同的基因，则先替换为相应数组中的元素再进行交换。设定一个交叉概率Pc，小于该概率时进行交叉。根据经验值Pc取0.6。

(7)算法终止条件。遗传算法的终止条件本质上即对于它与蚁群算法二者之间的最佳融合时机的判断。设置最小遗传迭代次数Genemin，最大遗传迭代次数Genemax，最小进化率Genemin-improv-ratio，最小进化率连续代数为Genedie。当满足以下条件之一，遗传算法终止：①遗传算法迭代次数达到Genemax；②迭代中连续Genedie代，子代优化解改进率都小于Genemin-improv-ratio。

2.3 蚁群算法部分

(9)

(10)

式中Q为调整系数，bij为效益系数。

(2)授权用户节点选择策略。蚂蚁按下式选择授权用户节点j。

(11)

(12)

式中，I为蚂蚁可能访问的节点的集合，其中不包含禁忌表中的元素。

(3)设置蚁群算法控制参数：α=β=1，信息素挥发率ρ=0.2，调整系数Q=10。

(4)蚂蚁数的设置：为认知用户节点数n。

(5)蚁群算法结束条件(满足其一即可)：①蚂蚁算法迭代次数达到Antmax；②迭代中连续Antdie代，子代优化解改进率都小于Antmin-improv-ratio.

2.4 衔接策略部分

(1)设置两种算法的动态融合时机：即遗传算法的终止条件。

(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算法的频谱分配明显优于基于CSGC算法的频谱分配。而依据图3可知基于GACO算法的频谱分配公平性也比基于CSGC算法的频谱分配更高、更稳定。

图2 GACO和CSGC的网络总效益比较

图3 GACO和CSGC的公平性比较

图4给出了可用频谱数M=30时平均效益随认知用户数N的变化曲线。由图知，基于GACO算法的频谱分配所得到的平均效益均大于CSGC算法获得的平均效益。

图4 N变化时的算法性能

图5给出了认知用户数N=20时平均效益随可用频谱数M的变化曲线。由图知，基于GACO算法的频谱分配所得到的平均效益均大于CSGC算法获得的平均效益。

图5 M变化时的算法性能

4 结语

合理有效地分配认知用户所需的频谱是认知无线网络提供可靠通信服务的关键。认知无线电频谱分配问题可以看做一个优化问题。将遗传算法或蚁群算法单独应用于该优化问题已有先例。本文汲二者之所长，使用GACO算法来求解该优化问题，并与颜色敏感图着色算法进行了性能比较。仿真结果表明基于GACO算法的认知无线电频谱分配方法能更好地提升网络效益、增加频谱分配的公平性。仿真过程中，一些初始值的设定，均采用了经验值，如何更好地优化这些初值将是本文深入探究的一个关键问题。

[1] 杨淼，安建平.认知无线网络中一种基于蚁群优化的频谱分配算法[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] 肖冬荣，杨磊. 基于遗传算法的关联规则数据挖掘[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

1002-0802(2015)11-1265-05