基于改进二进制灰狼算法的频谱分配

徐 航，张达敏，王依柔，宋婷婷，樊 英

(贵州大学 大数据与信息工程学院，贵州 贵阳 550025)

0 引 言

随着当今通信技术的快速发展，超高速、超高容量的5G技术也将在几年内商业化，而无线通信业务的增加导致无线频谱资源稀缺的问题日益严重，而且当前频谱资源的使用率低，存在较多的频谱空洞[1]，为了解决这一问题，许多专家提出了认知无线电(cognitive radio，CR)[2]，而动态频谱分配则是认知无线技术中的焦点问题，其主要通过动态感知授权频谱当前的使用状态，从而达到最大化频谱利用率的目的。

在CR系统中，一般用来实现动态频谱分配的模型有博弈论模型[3]、干扰温度模型[4]、拍卖竞价模型[5]和图论着色模型[6]等，由于这些模型在优化系统效益和用户间公平性等方面有比较明显的缺陷，所以许多研究将智能优化算法用于优化该问题。文献[7]提出了一种基于改进二进制粒子群算法的频谱分配策略，对粒子速度公式进行离散化改进，但算法难以得到最优解。文献[8]提出了基于改进遗传算法的频谱分配策略，但改进遗传算法仍然容易早熟，而且收敛速度较慢。针对传统的优化算法存在的缺陷，而相关研究结果表明许多群体智能优化算法[9,10]在工程领域也有不错的实用效果，本文采用群体智能优化算法来解决上述问题。

本文在图论着色模型的基础上，提出一个改进二进制灰狼优化算法(improved binary grey wolf optimizer，BGWO)来优化认知无线电频谱分配问题，实验结果表明，本文的二进制灰狼优化算法能有效提高系统效益和认知用户接入公平性，这对优化认知无线电系统的性能具有重要的意义。

1 连续灰狼算法

1.1 等级机制

自然界中的灰狼群具有严格的等级制度，受这种等级制度的启发，有人对灰狼算法(grey wolf optimizer，GWO)[11]进行了研究。在捕食过程中，整个灰狼群等级像金字塔形状一样排列，顶层的α狼决定狼群的所有行动，其它狼不断向头狼靠近；位于第二层称为β狼，负责协助α做出管理决策；第三层的δ狼和底层的ω狼，负责听从α及β的指令，主要作用是平衡种群内部关系，这种分层的等级制度使狼群能有序地从各个方位完成各种捕食任务。

1.2 数学模型

在灰狼算法中，首先对狼群的捕猎过程进行建模，对空间中随机生成的灰狼个体进行适应度评估，把适应度值最好的前3头灰狼分别记为α、β、δ，随着算法的进行更新狼群位置，最终到达最优解附近。在这个过程中，首先实现对猎物进的包围，更新公式如下所示

X(t+1)=X*(t)-A·D

(1)

D=|C×X*(t)-X(t)|

(2)

其中，X(t)为当前灰狼位置，X*(t)为当前猎物位置，t为当前迭代次数，A,C表示系数向量，定义如下

A=2ar1-a

(3)

C=2r2

(4)

其中，r1和r2为[0,1]的随机数，a表示一个随迭代次数增加由2线性递减到0的收敛因子，定义为

a=2-2t/Tmax

(5)

其中，Tmax为最大迭代次数。

当狼群发现猎物后，最靠近猎物的头狼α指挥等级较低的狼群执行捕杀任务，通过模拟狼群的捕食过程，不断迭代使狼群向最优解靠近，算法首先确认当前狼群中解的前3名，然后按照下式不断引导其它成员向最优解移动，更新狼群的位置

Dα=|C1×Xα-X|

(6)

Dβ=|C2×Xβ-X|

(7)

Dδ=|C3×Xδ-X|

(8)

X1=Xα-A1·Dα

(9)

X2=Xβ-A2·Dβ

(10)

X3=Xδ-A3·Dδ

(11)

(12)

1.3 二进制灰狼算法

GWO在提出之时是用于解决优化函数问题，而在本文频谱分配问题中要解决的是常见的0、1问题，因此需要通过特定的转换函数实现连续解空间到二元空间的转换，大多研究中常使用Sigmoid函数[12]来实现连续到离散域的转换，转换函数表达式如下

(13)

(14)

2 改进二进制灰狼算法

2.1 非线性收敛因子

在灰狼算法中，设置算法参数A来调节算法的勘探能力，当|A|≥1时，灰狼群将扩大搜索范围，即着重全局搜索阶段；当|A|<1时，灰狼群将收缩包围圈，对猎物发动攻击，即着重局部搜索阶段。根据式(3)可知，算法参数A是由参数a决定的，所以a可以较大程度影响算法的优化结果，但算法中a随着迭代次数的增加呈线性递减，为了合理平衡算法的全局和局部搜索能力，有必要对灰狼优化算法的参数a进行优化，本文提出了一个非线性收敛因子，公式如下

(15)

其中，t为迭代次数，ainitial表示a的初始值2，Tmax为最大迭代次数，由图1可知，在算法前期，随着迭代次数的增加，a从2非线性先缓后急递减，此时a减小速度缓慢，即a>1所占迭代次数比例更大，从而加强了算法的全局搜索能力；到迭代后期，a>1所占迭代次数比例减小，而且到后期减小速率明显加快，此时算法快速进行局部开发阶段，因此本文通过非线性收敛因子来加强算法的全局搜索能力。

图1 收敛因子a的对比

2.2 柯西扰动策略

GWO容易出现早熟等问题，为降低这些缺陷对算法的影响，在原始位置更新公式的基础上，提出一种带有柯西扰动算子的位置更新方案，主要思想是利用柯西变异的优势，扩大狼群的分布区域，从而减小算法局部早熟的概率。一维标准的Cauchy分布的概率密度函数[13]如下所示

(16)

Cauchy分布的概率密度曲线类似于一个钟形，峰值较小但在两端的分布长且平缓，无限接近于x轴而不与坐标轴相交，这种特征意味着通过柯西变异，可以产生与原点相距较远的随机数，也意味着经过Cauchy变异后的灰狼个体在一定程度上具备了可以迅速跳出局部最优区域的能力，同时，利用Cauchy分布峰值较低的特点可以减小变异后的个体在邻域周围搜索的时间。

2.3 自适应权重

在GWO中，如果α狼在某一代捕获到局部最优解时，将导致整个狼群向局部最优区域收敛，而且GWO在全局搜索和局部开发阶段时权重是固定的，受粒子群算法惯性权重的启发，同时为了提高局部搜索的能力，引入一个自适应的权重因子，不断地通过非线性权重的调整，从而强化算法跳出局部最优区域的能力。公式如下

(17)

其中，t为当前迭代次数，Tmax为最大迭代次数，ωmax=0.9，ωmin=0.4，k为控制ω曲线跳跃幅度的缩放因子，本文k=0.05，nTent表示由Tent混沌映射[14]产生的均匀随机数。上式中的前两项是为了实现权重非线性递减，且服从ω∈[0.4,0.9]，此时的权重能使算法发挥最优的寻优效果[15]；第三项的取值是为了实现了权重的动态变化，使算法在迭代前期权值较大时也能产生较小的权值，到迭代后期权重变化较小且平稳时也有机会获得较大的权值，进而提高算法收敛精度。综合以上改进策略后式(9)～式(12)的位置更新公式如下

X1=(Xα-A1·Dα)·(1+i·cauchy(0,1))

(18)

X2=(Xβ-A2·Dβ)·(1+i·cauchy(0,1))

(19)

X3=(Xδ-A3·Dδ)·(1+i·cauchy(0,1))

(20)

(21)

2.4 二进制灰狼算法

为了更好处理实际中的离散问题，连续域到离散域的研究也是必要的，有研究显示Sigmoid函数离散化后的算法会出现位置不变等缺点，因此本文引进一个新的离散转换函数[16]来实现频谱分配时的0、1转换操作

(22)

(23)

式中：rand为[0,1]分布的随机数，通过上述转换，将连续变量更好地转换为离散变量，进而提高整个频谱分配的效果。

3 基于灰狼算法的频谱分配

3.1 基于图论着色的频谱分配模型

本文利用灰狼算法实现频谱分配的目的是将频谱资源智能且有效地分配给认知用户，同时要满足主用户对于频谱资源正常使用的需求。假设在一个X×Y的区域中分布M个完全正交的可用频谱，存在I个主用户和N个认知用户，认知用户在不对其他用户(主用户和认知用户)产生干扰的前提下可以使用多个频谱，当主用户i(i=1,2,…,I)分配的频谱为m(m=1,2,…,M)，认知用户n(n=1,2,…,N)机会接入m时，则主用户在频谱m的覆盖范围是以i为中心rii,m为半径的圆形区域，认知用户n在频谱m的覆盖范围是以n为中心rnn,m为半径的圆形区域，假设用户间干扰只由用户的干扰距离决定，如图2所示，认知用户1会对主用户1产生干扰，所以认知用户1不能使用主用户1的授权信道，同理，认知用户2不能使用主用户2的授权信道，同时，认知用户间存在干扰，所以认知用户1、2不能同时接入同一授权频谱。

图2 认知无线网络拓扑结构

本文将认知无线网络的频谱分配建模为图论着色问题，用无向图的形式来表示用户间的关系，其中频谱分配涉及的空闲矩阵L、效益矩阵B、干扰约束矩阵C和无干扰分配矩阵A的定义同文献[17]。

定义1 用户效益R。R={βn}N×1，其中βn表示认知用户n在无干扰分配矩阵A的前提下，在M个信道上所取得的全部收益，表示为

(24)

则系统总效益U(R)表示为

(25)

定义2 最大系统效益Umax。认知无线网络频谱分配的目标即为最大化系统总效益U(R)，则频谱分配优化问题可表示如下

(26)

则最大平均系统效益表示为

(27)

定义3 认知用户接入公平性Ufair。其目标是确保频谱分配过程中认知用户的接入公平性。其公式定义为

(28)

在频谱分配问题的仿真阶段，为了更明显地验证频谱分配是否有效，将Umax、Umean和Ufair作为判断本文频谱分配系统是否有效的指标。

3.2 改进二进制灰狼算法的频谱分配

在本文提出的关于频谱分配优化的IBGWO算法中，每个领头狼α的位置使用一串二进制编码来表示，用于代表一个有效的频谱分配方案。求解最大系统总效益情况下的无干扰分配矩阵A是频谱分配的最终目标，通过上述空闲矩阵中认知用户使用信道的具体情况，可以确定矩阵A中的所有数字，若ln,m=0，表示认知用户n没有获得使用信道m的权限，这时对应A中相应位置的an,m一定为0；若ln,m=1，那么an,m可能为0或1，此时只需对矩阵中元素为1的位置进行编码，记录矩阵L中元素1的个数，即解的编码长度D，计算公式如下

(29)

在频谱分配模型中，狼群的初始位置编码是随机生成的，对于认知用户间的干扰也应该考虑其中，所以，需要对个体的位置进行约束处理。对任何信道m，首先确定C中满足cn,k,m=1的条件下所有n和k的情况，同时判断A中的an,m和ak,m的值是否满足同时为1的情况，假如均为1，则随机将其中一个1设置为0，按照上述流程完成后，才能将领头狼的位置编码达到无干扰约束的要求。如图3所示，假设在一个网络环境中，认知用户数N=5，信道数M=4，根据上述编码规则，可以得到解得编码长度为8(8维)，同时得到无干扰分配矩阵A。

图3 位置编码与矩阵A的映射关系

3.3 频谱分配算法流程

综上所述，本文频谱分配具体流程如下：

步骤1 初始化空闲矩阵L、效益矩阵B和干扰约束矩阵C，统计L中值为1的数量，并且记录值为1的位置上对应的n和m，即为L={(n,m)|ln,m=1}，L中的元素按n和m值递增的规则排序，确定算法编码长度；

步骤2 随机生成二进制编码(初始化个体位置)，设置种群规模、最大迭代次数等，并记录初始适应度值；

步骤3 对相关的矩阵完成干扰约束处理过程，分配矩阵A为α狼的位置的映射，随后判断C中满足cn,k,m=1的条件下的所有n和k，接下来确认A中an,m和ak,m的值是否一样，若均为1时，将an,m和ak,m的值随机一个设置为0，经过干扰约束处理后再对相应的解进行二进制编码；

步骤4 根据式(15)～式(17)更新算法参数，根据式(18)～式(20)来更新算法位置，寻找并更新全局最优解，并使用式(22)、式(23)进行离散操作；

步骤5 对产生的位置进行干扰约束处理，根据目标函数得到相应的适应度，并将最佳适应度值对应的位置保存为最优位置；

步骤6 若当前迭代次数t未超出最大迭代次数，则令t=t+1，并转到步骤4，否则算法终止，输出全局最优解和适应度值。

4 仿真实验和结果分析

为了评估本文所提算法在频谱分配应用中的有效性，同时验证每一种改进策略的效果，利用MATLAB搭建仿真模型，在相同的拓扑结构下以Umax和Ufair等指标作为优化目的，将本文所提算法(IBGWO)与二进制灰狼算法(BGWO)、蝙蝠算法(BA)、粒子群算法(PSO)、加入权重的灰狼算法(WGWO)、加入非线性收敛因子的灰狼算法(AGWO)和基于柯西扰动策略的灰狼算法(CGWO)进行30次频谱分配仿真实验。本文实验环境为Window10系统，16 G内存和2.9 GHzCPU。

假定在一个区域中，认知用户N=20，可用信道数M=10，各个算法参数设置为：种群大小为40，最大迭代次数Tmax=500，ωmax=0.9，ωmin=0.4，ainitial=2，k=0.5，i=0.6，蝙蝠算法中响度A=0.9，脉冲发射率r=0.7。

4.1 不同环境下的仿真实验

由于收敛速度和精度都是评价算法优劣的指标，图4为N=20,M=10时随机一次实验中各个算法的收敛曲线，可以看出系统效益随着迭代次数增加而增加，而IBGWO的最终系统效益远远高于其它算法，而且最终网络效益比最差的BA高出约40%；从收敛速度来看，由于IBGWO融合了其它算法的改进思想，所以收敛速度最快，且迭代到200次左右就趋于收敛，说明改进后的算法具有一定有效性，进而验证其可以在频谱分配时表现出较好的效果。

图4 系统效益和迭代次数的关系

为了验证算法在不同网络环境下的频谱分配效果，因此在N=20，M=10的条件下模拟环境中30种不同的分散情况，最终获得多种条件下的Umax和Ufair的目标曲线图。由图5和图6可以看出，在不同网络环境下，IBGWO获得的系统总效益和用户接入公平性的效果都比其它算法要好，说明加入的改进策略提高了灰狼算法的性能，可以准确快速地到达最优解附近，所以使IBGWO在不同网络环境下都能获得较高的网络效益和认知用户接入公平性，而且相对稳定，同时可以看出每一个加入改进点的算法都比原始算法的效果更好，说明文中所提及的改进点对算法的性能具有一定的促进作用。

图5 不同信道的系统效益

图6 不同信道的公平性

4.2 认知用户数对系统效益的影响

系统平均效益受很多因素影响，为了验证不同用户数量对系统平均效益的影响，设置环境中可用信道数M=10保持不变，认知用户数N从10递增到30，可以总结出使用频谱的用户数量和系统平均效益之间的关系，分析图7可知，保持环境中可用信道数量不变，如果不断增加系统中认知用户的数目，那么认知无线电系统的平均系统效益就会逐步减小，这是由于信道资源紧缺，才会导致系统平均效益呈下降趋势，但是IBGWO得到的平均系统效益仍然比其它算法要高，进而验证了本文所提二进制灰狼算法在频谱分配中的优越性。

图7 平均效益与用户数的关系

4.3 可用频谱数对系统效益的影响

由于环境中频谱数也会影响整个系统的效益，为了研究算法在不同信道数下的性能，设置认知用户数N=20保持不变，可用频谱数M从10递增到30，从图8可知，当某一区域中存在的空闲频谱数量增加时，认知用户可以接入频谱的机会也会相应增加，所以系统平均效益也逐渐增大，同时IBGWO的平均效益也高于其它算法，进而说明本文所提算法在频谱分配当中的有效性。

图8 平均效益与可用信道的关系

5 结束语

针对当前无线通信系统中频谱资源紧缺的难题，本文从收敛速度和收敛精度等方向对灰狼算法进行改进，最后将其用于优化认知无线电频谱分配问题，仿真结果表明：改进后的算法一定程度上优化了原始灰狼算法的缺陷，在解决认知无线电频谱分配问题时，可获得更高的系统效益和更高的认知用户接入公平性，达到频谱分配的最终目的。