基于二进制蜉蝣算法的频谱资源分配

郭爱心，芦 宾，王大为

(山西师范大学物理与信息工程学院，山西 临汾 041000)

无线电频谱是一种有限的稀缺资源。随着5G、未来无线网络等无线通信技术的发展和用户规模的激增，使得频谱供需矛盾也日益加剧。认知无线电技术为解决该问题提供了有效途径，认知无线电系统通过频谱感知技术自动感知、寻找空闲的频谱资源并将其按一定的分配策略分配给未授权用户(即认知用户)，实现频谱资源的二次分配，提高频谱利用率[1]。根据不同的应用场景和性能准则，频谱分配策略和模型也不尽相同，常用的有基于图论、博弈论和经济学中拍卖竞价的模型等[2-5]。基于图论的频谱分配是一个典型的NP-hard离散优化问题[6]，智能优化算法是解决此类问题的常用方法之一。智能优化算法受生物群体行为或自然现象规律等启发而提出，它在预定的搜索空间随机产生一组解，并根据解之间的信息迭代更新以找到最优解或次优解，具有全局寻优能力强、鲁棒性强、通用性强等优点。文献[7]将二进制粒子群算法(Binary Particle Swarm Optimization，BPSO)[8]用于频谱分配，并根据信道可用性矩阵的特征和干扰约束，提出了信道分配矩阵与粒子位置之间的映射过程，缩减了算法的搜索空间。文献[9]将离散人工蜂群算法(Discrete Artificial Bee Colony，DABC)引入到频谱分配，但存在冗余计算、算法收敛速度过慢等缺点。文献[10]基于多态蚁群优化算法，在信息素分配过程中考虑了分配时间因素，提高了信道利用率。智能优化算法性能对于频谱分配问题的求解至关重要，受算法性能的局限，目前频谱分配普遍存在收敛速度不快和寻优精度不高等问题。近年来，不断地有新型智能优化算法涌现出来，如蜉蝣算法(Mayfly Algorithm，MA)[11]、均衡优化器算法[12]、麻雀搜索算法[13]和蜻蜓算法[14]等。本文基于性能优异的蜉蝣算法提出了适用于离散域优化的二进制蜉蝣算法(Binary Mayfly Algorithm，BMA)，并将其应用于认知无线电的频谱资源分配中，以期提高频谱分配的收敛速度和寻优精度。

文献[11]于2020年提出了蜉蝣算法这一新型群智能优化算法。蜉蝣是一种有翅昆虫，若虫可在水中生活约1～6年，成年蜉蝣常在水面活动。成年蜉蝣的寿命极短，故有“朝生暮死”之说。在其短暂的生命历程中，雄性蜉蝣常成群聚集在水面并进行婚飞，雌性蜉蝣被雄性吸引飞入集群进行交配。蜉蝣算法就是受蜉蝣社会行为的启发而提出的。

对于待优化的问题，设其目标函数为F(x)，变量为x=(x1，…，xd)，d为变量维度。用蜉蝣算法在指定搜索空间进行寻优时，雄性蜉蝣的位置代表问题的可行解，蜉蝣根据其个体和群体行为及经验来寻找最优解，用适应度函数f(x)评价解的质量。若目标函数是寻找最小值，则适应度函数f(x)=F(x)，反之，则f(x)=1/F(x)，f(x)越小则表明解越优。

2.1 雄性蜉蝣的行为描述

(1)

其中，i=1，2，…，N，j=1，2，…，d。

(2)

其中，pbij表示第i个雄性蜉蝣个体历史最优位置的第j维的值；
gbj表示全局最优位置的第j维的值；
g为重力系数，g∈(0，1]；
a1、a2和β为平衡系数，a1∈[1，2]，a2∈[1，2]，β∈[1，2]；
rp、rg分别为雄性蜉蝣当前位置与个体历史最优位置、全局最优位置的笛卡尔距离，计算如式(3)、式(4)

(3)

(4)

(5)

其中，d为婚飞系数，r为[-1，1]间的随机值。

2.2 雌性蜉蝣的行为描述

(6)

(7)

(8)

其中，fl为飞行系数；
r1为[-1，1]间的随机值。

2.3 交配行为描述

假设雌雄蜉蝣配对按照“门当户对”进行，即最好的雌性和最好的雄性配对，第二好的雌性和第二好的雄性配对，并以此类推。在雄性和雌性蜉蝣种群中，取最优的一半进行交配，每一对蜉蝣可繁衍两个子代，这样既可保证参与交配的个体是优秀的又可使种群规模保持不变。子代蜉蝣的产生如式(9)和(10)：

offspring1=L*male+(1-L)*female

(9)

offspring2=(1-L)*male+L*female

(10)

其中，male和female为父代；
L为[-1，1]间的随机值。子代的初始速度置为零。

2.4 子代变异描述

为减少算法早熟陷入局部最优的情况，在种群中引入变异，变异子代的产生如式(11)

offspringn=offspringn+θ

(11)

其中，offspringn为产生变异的子代个体，θ为服从标准正态分布的随机数。

2.5 算法流程

由上述描述可知，蜉蝣算法以雄性蜉蝣的位置作为待优化问题的解，其算法流程如下：

算法1 蜉蝣算法

Step1：将蜉蝣群体随机分为相同个数的雌性和雄性蜉蝣；

Step2：初始化雄性蜉蝣位置和速度，计算适应度，记录个体最优位置和全局最优位置；

Step3：初始化雌性蜉蝣位置和速度，计算适应度；

Step4：更新雌雄蜉蝣的位置和速度，计算适应度并排序，更新个体最优位置和全局最优位置；

Step5：选取优秀的雌雄蜉蝣进行交配，产生子代，计算适应度；

Step6：将子代随机分为雄性和雌性蜉蝣，作为下一轮迭代的父代；

Step7：更新个体最优位置和全局最优位置；

Step8：重复Step4至Step7，直至满足迭代终止条件。

对于二进制离散优化问题，解参数只能是0或1，基于连续域的蜉蝣算法难以解决此类问题，故本文提出了二进制蜉蝣算法。由于解空间的离散化，蜉蝣速度和位置更新规则以及子代的产生和变异都应进行重新定义。

3.1 速度更新

在蜉蝣算法的速度更新式(2)和(7)中，rp、rg和rmf涉及到笛卡尔距离的计算，而在二进制蜉蝣算法中，蜉蝣位置由0和1构成，可看成一串01序列，本文引入汉明距离代替笛卡尔距离来度量当前蜉蝣位置与个体历史最优位置、全局最优位置及其配偶位置的关系，分别用rp1、rg1和rmf1表示。汉明距离表示两个位置对应位不同的数量，则式(2)和(7)改写为式(12)和(13)

(12)

(13)

3.2 位置离散化

(14)

(15)

由Sigmoid函数性质可知，当其自变量不在[-4，4]区间时，函数值逐渐趋于不变，这样会导致蜉蝣位置更新失效，算法陷入局部最优，故应按式(16)对速度的取值进行限制，式中取Vmax=4。

(16)

3.3 有向双点交叉

蜉蝣位置参数进行二值化后，其子代的产生可借鉴遗传算法中的交叉和变异操作。本文在遗传算法双点交叉的基础上，提出了有向双点交叉，用全局最优位置指导子代的进化方向。有向双点交叉首先在父代随机产生两个交叉位点，然后互换基因产生两个子代offn1和offn2，如图1所示；
然后通过全局最优位置指导子代的进化方向，产生有向交叉的子代offn3和offn4，如式(17)和(18)，其中，L1为随机产生的0-1矩阵；
最后对offn1、offn2、offn3和offn4的适应度进行比较，选取最优的两个子代作为后代。

图1 双点交叉示意图

offn3=L1·offn1+(1-L1)·gb

(17)

offn4=L1·offn2+(1-L1)·gb

(18)

有向双点交叉使得种群进化向着“优胜劣汰”的方向进行，便于寻找最优解。

3.4 按位变异

不同于蜉蝣算法，在二进制蜉蝣算法中，若子代发生变异，则随机选取m个位进行取反，获得变异后代。变异位的个数m取决于变异率和蜉蝣位置序列的长度，设变异率为mu，蜉蝣位置序列长度为l，则m=「mu×l⎤，本文取mu=0.01。

3.5 算法分析

由二进制蜉蝣算法的设计可知，其核心是位置的更新。由3.2节可知，位置离散化通过Sigmoid函数实现，其函数值表示蜉蝣位置对应位取1的概率。而蜉蝣位置的更新则依赖于位置向量中位的改变。

(19)

图位改变概率等高线图

在认知无线电系统中，用户可分为授权用户和认知用户，授权用户的优先级高于认知用户，对于未被授权用户使用的频段，可通过频谱分配技术分配给认知用户，提高频谱利用率。

4.1 图论频谱分配模型

本文选取图论频谱分配模型进行频谱分配，其具体定义如下：

1)可用频谱数M：描述当前未被授权用户使用的频谱数。

2)认知用户数N：描述系统当前认知用户总数。

3)频谱可用性矩阵L：N×M的二维矩阵，L={ln，m|ln，m∈{0，1}}N×M，描述频谱m对用户n是否可用，若可用，ln，m=1，若不可用，ln，m=0。

4)干扰约束矩阵C：N×N×M的三维矩阵，C={cn，k，m|cn，k，m∈{0，1}}N×N×M，描述用户n，k是否可以同时使用频谱m，若可同时使用，cn，k，m=0，若不可同时使用，cn，k，m=1。

5)频谱分配矩阵A：N×M的二维矩阵，A={an，m|an，m∈{0，1}}N×M，描述频谱分配策略，若an，m=1，表示此时段将频谱m分配给了用户n。显然频谱分配矩阵应满足无干扰分配原则，即：当cn，k，m=1时，an，mak，m=0。

6)效益矩阵B：N×M的二维矩阵，B={bn，m|bn，m∈R+}N×M，描述将频谱m分配给用户n获得的网络效益。

根据上述定义可知，频谱分配问题等价于寻找满足L和C的约束且使优化目标函数最大的频谱分配矩阵A，问题的可行解的集合表示为Λ(L，C)N×M。本文使用文献[15]中定义的最大和网络效益(Max Sum Reward，MSR)和最大比例公平网络效益(Max Proportional Fair，MPF)作为优化目标函数。最大和网络效益计算如式(20)：

(20)

最大比例公平网络效益计算如式(21)：

(21)

这两个目标函数分别代表不同的性能评价准则，UMSR用来评价网络平均效益，其目标是最大化频谱资源利用率，UMPF用来评价认知用户间的公平性，其目标是最大化频谱资源分配公平性。

4.2 频谱分配算法描述

求解最优的频谱分配方案即寻找目标函数的最大值。本文用二进制蜉蝣算法来进行寻优，步骤如下：

算法2 基于二进制蜉蝣算法的频谱分配

Step1：初始化图论频谱分配模型参数；

Step2：初始化二进制蜉蝣算法参数；

Step3：根据干扰约束矩阵C进行无干扰约束处理，将雄性蜉蝣位置与频谱分配矩阵A中的元素进行对应；

Step4：进行二进制蜉蝣算法迭代，记录每次迭代的个体历史最优、全局最优，更新蜉蝣位置、速度等相关参数，更新网络效益最优值；

Step5：检查是否满足终止条件，若不满足，重复Step4至Step5，若满足，输出网络效益最优值。

为验证二进制蜉蝣算法的有效性，本文利用Matlab软件进行了仿真，并将BMA算法与经典的BPSO算法[8]、DABC算法[9]及较新的二进制蜻蜓算法(Binary Dragonfly Algorithm，BDA)[14]进行比较。四种算法的种群规模均选取为20，做相同的初始化。BMA算法中的其它参数设置为a1=1，a2=1.5，a3=1.5，β=2，g=0.8，d=5，fl=1，BPSO[8]、DABC[9]、BDA[14]算法中其它参数与对应文献中的参数保持一致。效益矩阵B中元素取值范围设成[1，10]。

5.1 频谱资源利用率

为比较不同算法在网络资源利用率方面的表现，用最大和网络效益指标进行评价。仿真设定相同的网络环境，即网络参数M、N、L、C、B保持不变。设M=20、N=16，L、C、B通过随机数产生，最大和网络效益对比如图3所示，BMA算法收敛速度快且收敛后的最大和网络效益最大。为了进一步验证BMA算法对不同网络环境均具有优异的优化性能，本文设定了20种不同的网络环境(M=20、N=16保持不变)进行实验，结果如图4所示，BMA均能找到更好的频谱分配矩阵，获得更大的最大和网络效益。上述实验结果表明BMA算法收敛速度快、寻优能力强，能有效提高频谱资源利用率。

图3 同一网络环境不同算法的最大和网络效益对比

图4 不同网络环境不同算法的最大和网络效益对比

5.2 频谱资源分配公平性

为比较不同算法在频谱资源分配公平性方面的表现，用最大比例公平网络效益指标进行评价。同一网络环境(M=20、N=16，L、C、B随机产生并保持不变)不同算法的最大比例公平网络效益比较结果如图5所示，BMA算法在收敛速度和频谱资源分配公平性上表现最优，能更好地保证认知用户公平地接入空闲频谱。不同网络环境(M=20、N=16保持不变)不同算法的最大比例公平网络效益比较结果如图6所示，BMA算法均能找到更好的频谱分配矩阵，获得更大的最大比例公平网络效益。上述实验结果表明BMA算法收敛速度快、寻优能力强，能有效提高频谱资源分配的公平性。

图5 同一网络环境不同算法的最大比例公平网络效益对比

图6 不同网络环境不同算法的最大比例公平网络效益对比

5.3 认知用户和可用频谱对网络性能的影响

为探究BMA算法在认知用户数变化时的优化性能，本文在M=20，L、C、B不变的网络环境中，改变认知用户数进行实验，最大和网络效益和最大比例公平网络效益变化情况如表1和表2所示。由表1和表2可知，在可用频谱数不变的情况下，随着认知用户数的增加，用户竞争激烈，最大和网络效益和最大比例公平网络效益均呈下降趋势，但BMA算法的性能始终优于其它算法，体现出其对认知用户数变化有良好的鲁棒性。

表1 不同认知用户数下的最大和网络效益

表2 不同认知用户数下的最大比例公平网络效益

为探究BMA算法在可用频谱数变化时的优化性能，本文在N=20，L、C、B不变的网络环境中，改变可用频谱数进行实验，最大和网络效益和最大比例公平网络效益变化情况如表3和表4所示。由表3和表4可知，在认知用户数不变的情况下，随着可用频谱数的增加，认知用户的选择增多，最大和网络效益和最大比例公平网络效益均呈上升趋势，但BMA算法的性能始终优于其它算法，体现出其对可用频谱数变化有良好的鲁棒性。

表3 不同可用频谱数下的最大和网络效益

表4 不同可用频谱数下的最大比例公平网络效益

为提升频谱分配的效率和解的质量，本文提出了二进制蜉蝣算法并将其应用于频谱分配。在蜉蝣算法的基础上，本文对蜉蝣速度更新公式进行了重新定义，基于Sigmoid函数实现了位置更新的二值化，通过有向双点交叉和按位变异进行子代的产生和变异，完成了二进制蜉蝣算法的设计，并与其它具有代表性的算法BPSO、DABC和BDA进行了比较，实验结果表明BMA算法能够更好地利用和分配频谱资源，具有更快的收敛速度和更好的寻优能力。

推荐访问:蜉蝣 频谱 算法