近些年来,无线通信技术发展迅速,导致频谱资源变得紧缺[1]。认知无线电技术被公认为是提高频谱利用效率的有效方案,该技术通过对无线环境的感知、理解、判断和学习等方式,能够自适应地调整内部参数,以适应复杂多变的外部环境,最终实现对空闲频谱的检测和有效利用[2]。目前,频谱感知技术主要包括能量检测[3]、匹配滤波器检测[4]、周期平稳特征检测[5]等方法,由于实际的传输环境复杂而多变,单节点感知方法很难克服由隐藏终端、多径衰落及阴影效应等所带来的诸多不确定性问题,因此为了更好地解决这些问题协作式频谱感知方法应运而生。Quan等提出一种线性协作式频谱感知模型[6],但是该模型存在一个寻找最优向量的优化难题。
智能优化算法[7]是在对某一自然现象或过程进行抽象、简化和模拟的基础上建立起来的处理复杂优化问题的一类算法。差分进化算法(differential evolution,DE)[8]是优化算法的一种,具有很强的寻优能力,在一些领域得到成功应用[9-10],但该算法存在容易陷入早熟收敛,无法搜索到全局最优的缺陷。近年来,很多研究者致力于探索新的启发式算法。头脑风暴算法(brain storm optimization,BSO)[11]是一种模拟人类问题解决过程的新型群智能算法,全局搜索能力强,非常适合解决高维多峰的函数优化问题,所具备的优良特性使其得到许多关注和研究[12-14]。但现在对于该算法的研究仍然处于初级阶段,在实际优化过程中,针对一些复杂优化问题,仍存在收敛速度慢以及早熟收敛的问题。为了提高头脑风暴算法的性能,本文将差分进化算法引入到头脑风暴算法的创新操作中,提出差分头脑风暴算法(DBSO)。然后,将该算法应用于线性协作式频谱感知模型。通过与头脑风暴算法、混合蛙跳算法(SFLA)[15]和粒子群算法(PSO)[16]比较,在科学计算和实际工程背景下,验证差分头脑风暴算法的性能优势。
1 差分头脑风暴算法 1.1 差分进化算法差分进化算法的基本流程与其他的进化算法基本相同,包括变异操作、交叉操作和选择操作。
1.1.1 变异操作差分进化算法在实际的应用中变异方案形式多样,本文所用方案的变异方程如下所示:
(1) |
式中:xr代表被添加扰动的某个基础个体;xa、xb、xc和xd分别代表从父代群体中随机选择的4个个体;F代表变异因子,用来控制4个随机个体之间产生的2个差分矢量对基础个体产生的影响;xv代表通过此差分策略产生的变异个体。
1.1.2 交叉操作本文所用方案的交叉方程表示如下:
(2) |
式中:xv,j和xi,j分别代表变异个体xv和个体xi的第j维分量;xc,j代表通过此交叉方法得到的交叉个体xc的第j维分量;rand()代表 0~1 的随机值;CR∈(0,1)代表xv和xi之间的交叉率,其值的大小决定着xv和xi对xc的贡献同程度;jrand代表 1~D的随机正整数,用来确保xv对xc的贡献至少有一个分量,D代表个体的维度。
1.1.3 选择操作差分进化算法通过贪婪策略产生下一代个体,选择方程表示如下:
(3) |
式中:f(·)代表适应度函数;f(xc)和f(xi)分别代表xc和xv的适应度值;xig+1代表产生的下一代的第i个个体;g是当前迭代次数。本文中,根据所选适应度函数特点,适应度值越小,则认为个体越优秀。
1.2 差分头脑风暴算法作为演化算法的一种,差分进化算法通过模拟生物进化,经过反复迭代,使得具有最优适应度的个体被保留;由于该算法所依据的简单差分变异操作和竞争策略,能够使遗传操作的复杂性大大降低;同时,其独特的记忆功能使算法对当前的搜索情况动态跟踪,并不断地调整搜索策略,具有强大的鲁棒性和全局收敛能力。本节将差分进化算法纳入到头脑风暴优化算法中的创新操作中,通过差分策略在头脑风暴进程中的全局范围内产生尽可能多的解决方案,从而提高了头脑风暴算法跳出局部最优解的能力。
差分头脑风暴算法(DBSO)主要由分组、替换和创造3种操作来完成,通过模拟人类在问题解决过程中的行为,从而产生尽可能多的新解决方案,在一代又一代的迭代搜索中逐步寻找到最优方案。
假定在一个D维的目标搜索空间里,S={x1,x2,…,xN}代表N个个体组成的群体,xi=(xi1,xi2,…,xiD)代表群体中的个体i,其中i=1,2,…,N,根据适应度函数计算个体的适应度,把具有最优适应度值的个体作为全局最优个体xg。
1.2.1 分组操作通过分组操作将群体中N个个体聚类成M类,本文算法所用分类方法为K均值聚类方法。
1.2.2 替换操作对所有的M个分类依次从1~M循环执行替换操作。例如在第m(m=1,2,…,M)类中,首先寻找到该类中适应度最优的个体,记作此类的类中心,即中心个体;然后以一定的概率P1进行替换操作:当随机产生的概率r1<P1时,随机产生一个个体替换当前类的中心个体。
1.2.3 创新操作在创新操作中,通过当前个体xi和智能搜索策略产生的新个体yi=(yi1,yi2,…,yiD)的适应度对比来确定个体是否更新。首先,产生新个体yi的基础是通过智能搜索策略从当前群体中得到一个基础个体xs=(xs1,xs2,…,xsD)。该个体的产生策略有2种:一是当随机概率r2<P2时,随机选择当前某一个类,记为mx;当r2a<P2a时,选择该类的中心个体作为基础个体xs;当r2a≥P2a时,选择该类的一个随机个体作为基础个体xs。二是当r2≥P2时,随机选择2个类,分别记为my和mz,当r2b<P2b时连个类中选择中心个体的合并个体作为基础个体xs;当r2b≥P2b时,2个类中各选一个随机个体组成合并个体作为基础个体xs。然后,在xs基础上添加随机扰动得到yi。最后,根据适应度函数对xi和yi执行选择策略。则在xs基础上添加随机扰动过程如下:
1) 变异策略1
(4) |
(5) |
式中:xv,j和xs,j分别表示变异个体xv和个体xs的第j维分量;rj表示在xs,j上添加的随机扰动;r′j表示在上一代更新时添加的随机扰动,表示对过去搜索经验的记忆,使算法具有学习能力,因此具备更好的收敛性能;xa,j、xb,j、xc,j和xd,j分别表示父代群体中随机选择的4个个体xa、xb、xc和xd的第j维分量;N(0,1)表示均值为0方差为1高斯随机值。
2) 变异策略2
(6) |
(7) |
式中rj不包括父代的搜索经验记忆,使得算法能够扩大搜索范围。
3) 变异策略3
(8) |
(9) |
此策略中是在父代最优个体xg的基础上进行变异,能够促进算法朝着全局最优解的方向进化。
根据变异策略1得到变异个体xv后,根据差分进化算法的交叉原理得到新个体yi,公式为
(10) |
然后依据选择策略,如果yi的适应度值优于个体xi,则替换xi;否则执行变异策略2。
根据变异策略2得到变异个体xv后,根据式(10) 得到新个体yi,根据选择策略,如果yi的适应度优于个体xi,则替换xi;否则,执行更新策略3。
根据变异策略3得到变异个体xv后,根据式(10) 得到新个体yi,根据选择策略,如果yi的适应度优于个体xi,则替换xi。
在DBSO算法中,还有2个方面的问题需要特别注意。一个问题是yi中每一维分类yi,j的尺度问题,当超出设定的范围时,可设置其值为所超出边界的边界值;另一个问题是当通过2个类中的个体来产生基础个体xs时,被选中的2个中心个体或2个随机个体的合并个体可用以下公式表示:
(11) |
式中:R为0~1之间随机数,xmy和xmz分别为选中的类my和mz的中心个体或某个随机个体。
1.3 差分头脑风暴算法流程根据上述的分析与介绍,差分头脑风暴算法步骤如下所示:
1) 初始化参数,种群个数N,个体维度D,最大迭代次数G,分类个数M,概率P1,P2,P2a,P2b,以及交叉率CR。
2) 在目标问题可行解范围内随机产生N个个体,并根据适应度函数计算每个个体的适应度,并记录全局最优解xg。
3) 设置初始化迭代次数g=1,待更新个体初始索引号i=1。
4) 根据K均值聚类方法将群体分为M类。
5) 对于每一个类执行替换操作。
6) 对于个体xi,执行创新操作。如果i=N成立,则当前代中的所有个体更新完毕,执行步骤7);否则令i=i+1,继续执行步骤6),开始更新下一个个体。
7) 比较所有分类中的个体,把具有最优适应度的个体作为本次迭代的最优个体xg并记录最优值。
8) 若g=G成立,代表达到最大迭代次数,算法终止;否则,令g=G+1,返回步骤4)继续执行。
1.4 差分头脑风暴算法的测试基于MATLAB软件仿真平台,本节分别对提出的差分头脑风暴算法(DBSO)、头脑风暴算法(BSO)、混合蛙跳算法(SFLA)以及粒子群算法(PSO)4种群智能优化算法应用4种测试函数进行了收敛性能仿真测试。所选基准函数为Rosenbrock函数、Griewank函数,Zakharov函数和Sum Squares函数。4个函数公式分别为
(12) |
(13) |
(14) |
(15) |
4种智能算法的种群总数均设置为N=50,个体所处位置的维度为D=40,迭代次数均为G=1 000,独立运行200次实验。其中,SFLA算法的分组数目与BSO的分组数一致,都是M=10,其他参数设置参考文献[15]。PSO算法的参数设置参考文献[16]:速度变化范围限制为定义区间的10%,学习因子设置为c1=c2=2。DBSO算法和BSO算法具有一些相同的参数值,分类个数M=10,其中P1=0.2、P2=0.8、P2a=0.4、P2b=0.5,DBSO算法中CR=0.68,BSO算法中其他参数参考文献[11]。
仿真后的收敛曲线如图 1~4所示。从仿真图 1~4可以看出,相对于BSO、PSO和SFLA算法,DBSO算法对4个测试函数的收敛精度要远远优于其他3种智能算法。
2 基于差分头脑风暴的协作频谱感知 2.1 线性协作式频谱感知模型本文通过一种有效的频谱感知框架来构建多个认知用户之间的相互合作模式,并且能够准确地检测到不同认知用户不同形式的微弱信号[17]。即每个认知用户节点通过能量检测感知算法得到本地统计量,然后通过控制信道把本地统计量传送到模型的融合中心,融合中心再根据一定的策略来对各个统计量进行线性组合,最后依据判决门限进行判决。协作式频谱感知框架如图 5所示。
假设在认知无线电网络中有D个认知用户,则第j个用户的本地感知在第k个时隙的二元假设检验模型如下所示:
(16) |
式中:j=1,2,…,D;H0代表所监测信道不存在主用户信号;H1代表所监测信道存在主用户信号;gjk代表第j个认知用户接收到的信号;sk表示主用户发送的信号;hj表示信道衰减,在本文中认为信道衰减为常数;vjk表示加性高斯白噪声,其均值为零,方差为σj2;用σ=(σ12,σ22,…,σD2)T表示方差向量。
在采样间隔内经过Ns点采样之后,第j个认知用户采用能量检测进行本地感知,所计算的判决统计量用式(17)表示:
(17) |
将判决统计量uj通过控制信道传送到融合中心,融合中心接收到的各个统计量为
(18) |
式中nj表示来自控制信道的加性噪声,其均值为零。方差向量用(δ=δ12,δ12,…,δD2)T来表示。
根据接收到的各个统计量yj,融合中心依据式(19)来计算全局统计量yc:
(19) |
式中wj表示权重系数,代表特定认知用户的本地检测结果对全局判决结果的影响。也就是说,如果一个认知用户接收到高信噪比的信号,那么此用户的本地统计量对全局判决具有比其他统计量较高的贡献,因此本地统计量应该被分配一个较高的权重系数;相反,如果一个认知用户接收到的信号受到阴影和衰落的严重影响,则其统计量应该被分配一个较小的权重系数。用w=(w1,w2,…,wD)表示权重向量。
融合中心将全局统计量与门限值γc进行比较。如果yc≥γc,融合中心判决主用户信号存在;否则,判决主用户信号不存在。
根据以上线性协作式频谱感知模型,虚警概率可表示为
(20) |
检测概率可表示为
(21) |
式中:
根据式(20),门限值γc可通过虚警概率表示为
(22) |
把式(22)带入到式(21),可得检测概率的表达式:
(23) |
因为Q函数是一个单调递减的函数,所以,实现检测概率pd的最大化等同于实现下式的最小化,称此函数为频谱感知目标函数,表示为
(24) |
用差分头脑风暴算法直接优化式(24),则协作频谱感知模型的最大检测概率的问题就转化为下列优化函数:
(25) |
由式(25)可知,模型的最优解决定于权重向量w*。如果w*是使得模型得到最优解的权重向量,则权重向量λw*同样可能使模型得到最大检测概率。因此,需要对权重向量进行归一化处理,则约束优化问题转化为
(26) |
假设差分头脑风暴算法的某个个体表示为xi,则此线性协作频谱感知模型的适应度函数表示为
(27) |
则式(27)的最优解就是使式(26)最小化的最优权重向量。
该算法要求权重向量归一化,即需要根据频谱感知模型计算适应度的所有个体都要进行归一化,对于第i个个体进行归一化约束的方法为
(28) |
式中:xi=[xi1,xi2,…,xiD]表示个体的过渡位置;xi=xi1,xi2,…,xiD表示满足归一化条件的位置。
3 仿真实现与结果分析在仿真过程中,通过把差分头脑风暴算法(DBSO)、头脑风暴算法(BSO)、混合蛙跳算法(SFLA)以及PSO算法分别应用到线性协作式频谱感知这个工程问题中,对4种算法的全局搜索性能进行了分析比较。设置种群大小N=50;每种算法的迭代次数均为G=100,独立运行200次实验;参与协作频谱感知的认知用户个数为40,即4种智能算法中个体所处位置的维度为D=40;权重向量w的维度与算法个体的维度相同,由此完成了算法个体与待优化权重向量之间的映射;其他参数设置与测试基准函数时的参数值保持一致。假设主用户信号sk=1,每个采样间隔内的采样次数为Ns=20,模型中加性高斯白噪声的方向向量σ、控制信道的噪声方差δ以及信道增益向量h的向量维数和认知用户数量保持一致,σ每一维的值设置为1.3~2.3的随机值,δ每一维的值设置为0.4~3.8的随机值,h每一维是值设置为0.2~0.7的随机值。在虚警概率pf=0.15时,频谱感知目标函数和检测概率随着迭代次数的变化曲线如图 6、7所示。
从图 6、7可以看出:随着迭代次数的逐渐增加,4种智能算法在协作式频谱感知模型中的收敛结果不断的优化;与SFLA和PSO算法相比,DBSO算法能够获得更高的检测概率,与BSO算法相比,DBSO算法具有更快的收敛速度,几乎是BSO算法收敛速度的4倍,说明应用于频谱感知问题时,该算法能够在相对比较短的时间内获得很高的检测概率。
4 结论为了结合头脑风暴算法求解协作式频谱感知问题,针对头脑风暴算法收敛速度慢、易陷入局部最优的缺点,本文将差分进化算法的演进过程引入到头脑风暴算法的创新操作之中,提出了差分头脑风暴算法。
1) 通过基准函数的测试,验证了该算法具有很强的开发探索能力,是对头脑风暴算法的有效改进。
2) 提出的基于差分头脑风暴的线性协作式频谱感知算法,获得了更高的检测概率和更快的收敛速度,在工程应用的背景下证明了该算法的优越性。
3) 下一步工作可利用量子计算的优势对头脑风暴算法进行性能改进;或将差分头脑风暴算法应用到其他的工程实践中去,扩大算法的应用范围。
[1] | HAYKIN S, THOMSON D J, REED J H. Spectrum sensing for cognitive radio[J]. Proceedings of the IEEE , 2009, 97 (5) : 849-877 DOI:10.1109/JPROC.2009.2015711 |
[2] | HAYKIN S. Cognitive radio: brain-empowered wireless communications[J]. IEEE journal on selected areas in communications , 2005, 23 (2) : 201-220 DOI:10.1109/JSAC.2004.839380 |
[3] | PENG F, CHEN H, CHEN B. On energy detection for cooperative spectrum sensing[C]//IEEE 46TH Annual Conference on Information Sciences and Systems (CISS). Princeton, USA: IEEE, 2012: 1-6. http://cn.bing.com/academic/profile?id=1997740236&encoded=0&v=paper_preview&mkt=zh-cn |
[4] | JIANG C G, LI Y Y, BAI W L, et al. Statistical matched filter based robust spectrum sensing in noise uncertainty environment[C]//2000 IEEE 14th International Conference on Communication Technology (ICCT). Chengdu, China: IEEE, 2012: 1209-1213. http://cn.bing.com/academic/profile?id=2090181954&encoded=0&v=paper_preview&mkt=zh-cn |
[5] | 漆渊, 彭涛, 钱荣荣, 等. 认知无线电中基于循环平稳特征的频谱感知方法[J]. 重庆邮电大学学报: 自然科学版 , 2009, 21 (3) : 353-357 |
[6] | CUI T, GAO F F, NALLANATHAN A. Optimal of cooperative spectrum sensing in cognitive radio[J]. IEEE transactions on vehicular technology , 2011, 60 (4) : 1578-1589 DOI:10.1109/TVT.2011.2116815 |
[7] | 雷秀娟. 群智能优化算法及其应用[M]. 北京: 科学出版社, 2012 . |
[8] | STORN R. Designing nonstandard filters with differential evolution[J]. IEEE signal processing magazine , 2005, 22 (1) : 103-106 DOI:10.1109/MSP.2005.1407721 |
[9] | GUO Z Y, QIANG A, CHENG B, et al. Research on work roll temperature with improved differential evolution in hot strip rolling process[J]. Journal of system simulation , 2007, 19 (21) : 4877-4880 |
[10] | SINGH H, SRIVASTAVA L. Modified differential evolution algorithm for multi-objective VAR management[J]. International journal of electrical power & energy systems , 2014, 55 : 731-740 |
[11] | SHI Y H. Brain storm optimization algorithm[C]//Proceedings of the 2nd International Conference on Advances in Swarm Intelligence. Berlin: Springer, 2011: 1-3. http://cn.bing.com/academic/profile?id=137929096&encoded=0&v=paper_preview&mkt=zh-cn |
[12] | XUE J Q, WU Y L, SHI Y H, et al. Brain storm optimization algorithm for multi-objective optimization problems[C]//Proceedings of the 2nd International Conference onAdvances in Swarm Intelligence. Berlin: Springer, 2012, 513-519. |
[13] | QIU H X, DUAN H B. Receding horizon control for multiple UAV formation flight based on modified brain storm optimization[J]. Nonlinear dynamics , 2014, 78 (3) : 1973-1988 DOI:10.1007/s11071-014-1579-7 |
[14] | 沈林. 基于头脑风暴算法优化的v-SVR的研究及应用[D]. 兰州: 兰州大学, 2014. http://cdmd.cnki.com.cn/article/cdmd-10730-1014304039.htm |
[15] | EUSUFF M M, LANSEY K E. Optimization of water distribution network design using the Shuffled frog leaping algorithm[J]. Journal of water resources planning and management , 2003, 129 (3) : 210-225 DOI:10.1061/(ASCE)0733-9496(2003)129:3(210) |
[16] | KENNEDY J, EBERHART R. Particle swarm optimization[C]//Proceedings of 1995 IEEE International Conference on Neural Networks. Perth, Australia: IEEE, 1995. http://cn.bing.com/academic/profile?id=2152195021&encoded=0&v=paper_preview&mkt=zh-cn |
[17] | YUCEK T, ARSLAN H. A survey of spectrum sensing algorithms for cognitive radio applications[J]. IEEE communications surveys & tutorials , 2009, 11 (1) : 116-130 |