基于改进麻雀搜索算法的认知无线电频谱分配

张金飞，岳文静，陈 志

(1.南京邮电大学 通信与信息工程学院，江苏 南京 210003；2.南京邮电大学 计算机学院，江苏 南京 210023)

0 引 言

近年来，随着第五代移动通信技术(5G)的应用越来越广泛，无线电通信技术也被应用到各种新型无线设备中，随之也带来了一系列的问题，如无线通信业务量急剧增加、无线电频谱资源严重缺乏等。频谱资源作为国家具有战略地位的资源，深入影响着国民经济的发展，同时又不可再生。所以合理利用频谱资源，提高频谱利用率成为众多学者和研究人员关注的话题。由于认知无线电(Cognitive Radio，CR)技术可动态探测无线环境，能够实现频谱资源的共享，因此，该技术受到了广泛的关注。认知无线电可以通过动态管理频谱资源从而提高频谱利用率，无线通信的质量也得到一定程度的提高，是目前解决频谱资源短缺问题的有效方法之一。

随着技术不断进步，研究学者对认知无线电频谱分配的方案取得了一系列崭新的成果。通常将群智能搜索算法与认知无线电中的频谱分配问题相结合以解决问题。例如经典遗传算法、蚁群算法、二进制粒子群算法以及人工蜂群算法等。文献[1]通过在蚁群算法中信息素分配时加入一个时间因子，并对信息素排序，进而将信道分配给认知用户。文献[2]提出了一种改进的粒子群算法来优化频谱资源分配，该算法一定程度上提高了网络效益，但当信道数较大时，算法的效率较低。文献[3]给出了一种多策略更新信息素的蚁群算法，使用混沌初始化和混沌扰动对信息素进行依次更新，再对干扰约束条件进行了调整，进而求得最优解。该算法在一定程度上提高了平均网络效益，并未将频谱分配的公平问题考虑在内。文献[4]通过引入一个自适应概率阈值和自适应权重，提出了一种改进鲸鱼算法的方案来优化频谱分配，虽然提高了算法的收敛速度，但是当认知用户之间频谱使用的竞争增大时，网络的公平性也会进一步降低。文献[5]在基本狼群算法的基础上结合了量子进化算法与精英选择算子，精英选择算子的引入在一定程度上提高了算法的求解精度，但是该算法易陷入局部最优，很容易丢掉全局最优解。文献[6]提出了一种新型的智能搜索算法——麻雀搜索算法，模拟自然界麻雀捕食时的团队协作关系，即捕食与反捕食行为。采用该群智能优化算法来获得全局优化问题中的最优解。文献[7]则将克隆操作引入到海鸥算法中，扩充海鸥个体的多样性，进而通过人工免疫算子计算出适应度最佳个体。文献[8]介绍了频谱分配的三种模型，主要对图论着色模型展开论证，重在理论研究。文献[9-11]对麻雀搜索算法步长等参数做了一定的改进，但仍可优化。文献[12]则对频谱实现动态化分配管理，结果缺乏对比。文献[13-17]主要对网络的主要参数进行修改，缺乏具体的现实意义。因此，该文就认知无线电网络中常见的频谱分配优化问题，提出了一种改进的麻雀搜索算法。首先，种群初始化时采用透镜成像反向学习策略，在最优麻雀位置基础上继续寻优，便于最佳位置的搜索；然后，采用变步长设计，使用衰减因子来提高SSA算法的收敛速度；最后，对侦查预警的麻雀位置引入Levy策略进行更新，提高算法总体寻优的能力，在极大程度上节约了频谱分配所需时间，提高了信道使用效率。

1 频谱分配模型

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

在认知无线电网络中，可将用户分为主用户和认知用户。当认知用户只有在满足干扰约束条件时才可以使用不被占用的信道资源，同时不能影响主用户与外界正常的数据传输，这样认知用户和主用户共同使用固有的频谱资源，就可以通过频谱资源共享技术提高频谱资源利用率。通常频谱共享的方式有以下两种：一是利用控制信道得到所需要的信号资源;二是通过认知无线网络中的基站取得频率资源占用状况。该文将认知无线电网络频谱分配问题建模为图论着色问题。图论着色中频谱分配问题可用信道矩阵L、频谱效益矩阵B、干扰约束矩阵C以及无干扰频谱分配矩阵A等参数来描述。对其相关参数的说明如下：

(1)可用信道矩阵L：

L={ln,m|ln,m∈{0,1}}N×M，表示在该段时间中信道不被占用，系统中可以分配给认知用户使用的信道。当ln,m=1时，代表信道m有资源分配给认知用户n;当ln,m=0时，代表信道m中没有空闲资源供认知用户n使用。

(2)频谱效益矩阵B：

B={bn,m}N×M，是指信道m分配给用户n使用获得的效益。B为一个N×M的实数矩阵，bn,m表示认知用户n使用信道m时所能获得的最大效益。显然当ln,m=0时，则有bn,m=0。

(3)干扰约束矩阵C：

C={cn,k,m|cn,k,m∈{0,1}}N×K×M，表示当认知用户n和k在该时刻可以共同使用信道m通信，干扰矩阵C用来判断认知用户之间是否造成了干扰。当cn,m,k=1时，表示次用户n和次用户m会造成相互干扰。反之，当cn,m,k=0，则表示不会造成相互干扰。此时，用户n和用户k可共享信道m。

(4)无干扰频谱分配矩阵A：

A={an,m|an,m∈{0,1}}N×M，表示主用户不被影响且次用户之间互不干扰时的信道分配。an,m=1表示将信道m分配给次用户n，反之，信道m不能分配给用户n使用。该矩阵要满足L和C所规定的约束条件。

(5)用户效益R：

R={βn}N×1，其中βn表示在无干扰分配矩阵A下，次用户n在所有信道上获得的收益。公式为：

(1)

则系统总收益UR表示为：

(2)

(6)认知用户接入公平度Ufair：

为认知用户的比例公平度的最大值，主要是确保频谱分配过程每个认知用户获取近似相等概率的效益。公式为：

(3)

1.2 认知无线电网络分配频谱模型

认知无线电网络中，主用户的出现是不确定的，且其对信道的使用是随机的，认知用户检测到的信号是不断发生变化的。当认知用户的信道分配发生冲突时，信道分配问题在约束条件下可转为图论着色问题。频谱分配中的图论着色模型是根据主用户与认知用户之间，以及认知用户之间对某个信道的使用，并将这种关系抽象成网络拓扑图G(V,E,L)。V是图中所有顶点的集合，代表频谱分配模型中的所有认知用户；E是图中所有顶点之间边的集合，代表频谱分配模型中认知用户之间存在干扰；L为信道可用状态矩阵，表示每个顶点可以选择的颜色集合。

图1为主用户和认知用户组成的网络拓扑，信道A-D分别代表四个主用户授权的信道，S1-S5为五个认知用户，图中主用户所覆盖的通信范围可由图中的虚线圆表示，直线则代表认知用户之间存在一定程度的干扰。当认知用户处在主用户的通信覆盖范围之内，就会对该主用户的通信造成干扰，所以认知用户便不能利用该频段进行通信。图中每个认知用户括号内的频谱则是该用户的可用频谱集。例如S1可以使用的信道为B、C、D。

图1 认知无线限电网络拓扑

2 麻雀搜索算法

麻雀是杂食性群居鸟类，相比于其他鸟类，更具有团体协作意识。麻雀搜索算法是受自然界中麻雀的觅食行为的启发，将麻雀觅食过程构造成算法最优值的求解过程来进行搜索。SSA将麻雀分为三种类型：分别是发现者、加入者和侦察者，每种类型承担不同的功能。发现者担负着为种群寻找生存食物的职责，拥有最大的适应度值，加入者和侦察者会紧跟着发现者的位置变化来获取食物；加入者为种群主体，它们一直跟随发现者以得到充足的食物，同时不断与其他同类抢夺食物以维持生存；侦察者负责种群的安全，捕食过程中当意识到有危险靠近时会立即发出逃离信号，整体麻雀迅速向安全区域移动更新位置，做出反捕食行为。

(1)麻雀发现者的位置移动公式如下：

(4)

式中，t代表SSA搜索时每次进行迭代的次数，T代表最大迭代次数，α为[0,1]的随机数。xi,j(t)表示第i只麻雀在第j维的位置，Q是一个随机常数且取值服从正态分布，L表示一个1×d且元素值都为1的矩阵，R2∈[0,1]表示预警值，ST∈[0.5,1]为设定的安全值。当R2

(2)麻雀加入者的位置移动公式如下：

xi,j(t+1)=

(5)

式中，xworst(t)表示第t次迭代中麻雀种群的全局最差位置，xbest(t)表示第t次迭代中的全局最优位置即最容易获取到食物的麻雀位置。A表示一个1×d且元素随机赋值为1或者-1的矩阵，且A+=AT(AAT)-1。当i>n/2时，表示适应度值较差的第i只麻雀加入者无法捕获到食物，此时需要飞往其他的地方来继续搜索食物。

(3)麻雀侦察者的位置移动位置公式如下：

(6)

式中，xbest(t)表示第t次迭代中麻雀的全局最佳位置，β为服从均值为0、方差为1的正态分布的随机数，K∈[-1,1]代表麻雀的前进方向，可以控制步长参数，fi表示个体适应度值，fg为最大适应度值，fw为最小适应度值，e是为了防止分母为零的情况出现而设定的一个最小常数。当fi>fg时，表示麻雀处于种群的最外侧,易失去食物或受到捕食者攻击，当fi=fg时，表示处于种群内部的麻雀察觉到周边有危险存在，因此需要提醒种群逃离以免被捕食。

3 改进的麻雀搜索算法

基本麻雀算法在寻优过程中较易陷入局部最优解，为增强算法全局搜索能力，通过对影响算法搜索的主要参数进行调整，可改善寻优效果。

3.1 透镜成像反向学习策略

反向学习是一种为解决群智能算法在搜索过程中因陷入局部最优的情况而提出的优化机制，通过对当前搜索范围中最佳位置的反向点进行探索，扩大了搜索范围，更易找出最优解。将群智能搜索算法与反向学习策略在一定情况下进行结合可以有效提高方法的寻优性能。为解决SSA算法在求解过程中易陷入局部最优问题，该文引入凸透镜成像原理来帮助SSA算法跳出局部最优问题，即在当前最优麻雀位置上通过透镜成像找到最优点的反向点，然后在反向点的基础上继续向其他区域进行寻优求解。原理示意图如图2所示。

图2 透镜成像反向学习示意图

在一维有限空间ab中，存在个体p的高度为H，该点映射在坐标轴上为最佳位置x。凸透镜的中心点为o，f是凸透镜的焦距。通过凸透镜成像原理可以得到p的对应个体p*，高度为h，即为映射在坐标轴上的最优位置x*。根据凸透镜成像原理可以得出：

(7)

设H/h=n,可计算得到x*的表达式为：

(8)

通过调整n取不同的值，可以得到不同位置的反向点，即产生新麻雀个体的最佳位置。当n=1时，即为一般的反向学习策略。可以看出，通常所指的反向学习是透镜成像反向学习的一个特例，一般反向学习的反向点是固定的，而透镜成像反向学习通过调整n的值，得到的是一个动态变化的反向点，从一定程度上提高了求解精度。该文设置n=10 000。因为最优个体较一般个体拥有更佳的搜索位置，所以通过双透镜成像反向学习机制，可以避免SSA算法陷入局部极值问题，进而使算法的求解更加精确。

3.2 步长调整

在标准SSA算法中，加入者为麻雀种群中数量最多的个体，通过对加入者中麻雀个体的步长进行调整，可以改善整体的寻优性能。式(2)中的步长参数Q对平衡局部搜索和全局寻优能力具有重要作用，但Q每次为随机取值，在每次对最优解空间进行探索时，很容易陷入局部最优的状况。为了平衡局部精度和全局最优之间的关系，该文采用在进行初始查找时使用较大的步长，后面随着迭代次数的不断增加，步长比例性减小的方式。改进后的公式如下：

Q(t)=k·Q(t-1)

(9)

式中，t为当前迭代次数，k为步长衰减系数，通常k∈[0.7,1]。

3.3 Levy飞行策略

生物种群在自然界中进行觅食时，其捕食方式大多可看作是一种Levy飞行策略。Levy飞行是一种非高斯随机步态，它的特点是在小步长更替过程中会随机出现大步长。由于步长具有不确定性的特点，Levy飞行策略的步长比布朗运动的步长增长的更加快速且更具有随机性。当觅食者在未知环境中较大范围地搜索食物时，Levy飞行策略具有比布朗运动更加良好的搜索效果。传统SSA在最优值求解过程中，容易陷入到局部极值的困境。由于Levy飞行进行的是高频短距离的探索和低频长距离的交替探索，在寻找最优解过程中，引入Levy飞行可以在局部搜索和全局搜索时，分别采用不同长度的步长展开搜索。这样当搜索接近最优值时，选用合理的步长进行搜索，可以有效提高算法的收敛精度，解决标准SSA陷入局部最优的问题。该文在麻雀侦察者更新公式中加入Levy飞行策略，提高全局搜索能力。改进后的公式如下：

xi,j(t+1)=

(10)

其中，d为向量维度，Levy计算公式为：

(11)

(12)

其中，Γ(x)=(x-1)!，Q为服从正态分布的随机数，r3,r4∈[0,1]，ξ是一个可以调节的常数，通常可取值为1.5。

3.4 算法步骤

ISSA运行伪代码如下：

步骤1：初始化相关参数，如麻雀数量popsize、最大迭代次数iterMax、麻雀中发现者数量PD、侦察者数量SD、安全值ST、预警值R2等。

步骤2：分别计算种群中各个麻雀的适应度值并排序，找出当前最优值和最差值，及最优值和最差值对应的麻雀位置。

步骤3：参照式(4)和式(8)，使用透镜成像反向学习策略对PD中的最优和最差位置进行更新。

步骤4：参照式(5)和式(9)，动态调整步长因子，对加入者中麻雀位置进行更新。

步骤5：参照式(6)、式(10)和式(11)，在每次迭代中使用Levy飞行策略对侦察者SD中麻雀位置进行更新。

步骤6：判断是否达到最大迭代次数Max_iter，是则跳出循环；否则依次重复步骤3～步骤5。

步骤7：输出最优麻雀位置和最佳适应度值。

4 仿真与分析

为验证提出的ISSA算法在认知无线电频谱分配中的性能，考虑从系统总效益、认知用户接入公平性、收敛速度等方面出发，通过与传统遗传算法(GA)、粒子群算法(PSO)、海鸥算法(SOA)及初始麻雀搜索算法(SSA)进行对比，分析其性能优劣。

4.1 参数设置

实验采用Matlab2019b编写算法和仿真实现，条件假设无线网络环境中只存在用户间的干扰，不考虑环境中其他因素的影响。实验仿真设定认知无线电频谱分配网络区域为1 000×1 000，将算法的各项参数分别设置为：认知用户数N=20，可用信道数M=10，默认主用户数K=10，种群规模为20，迭代次数最大取为300次。

4.2 结果分析

实验主要选择三个性能指标进行分析，其中网络总效益指的是所有认知用户在指定信道下获得的网络效益(带宽)；认知用户接入公平性是确保频谱分配过程每个认知用户获取效益的机会均等；收敛速度可体现算法对系统变化的敏感度。

图3为选取网络总效益为目标函数和迭代次数进行比较，绘制了五种算法进行30次寻优操作的平均曲线，且以下图均为30次取平均的结果。此时信道数M和认知用户数N为固定值。由图3可知，随着迭代次数的增大，网络总效益不断增加，并逐渐稳定于一个常数。且改进后的麻雀搜索算法具有最大的网络总效益，收敛速度也较其他算法更快。

图3 迭代次数与网络总效益关系曲线

图4为网络效益与可用信道数的关系曲线，此时认知用户数固定，N=20。可以看到，网络效益随着可用信道数的增加而提高，这是因为在相同条件下，认知用户能够使用的信道数越多，该用户获得的收益也越大，可以看出ISSA算法的网络效益也超过了其他算法。

图4 可用信道数与网络效益关系曲线

图5 认知用户数与网络效益关系曲线

图5是在认知用户数从10增长到30的情况下，保持可用信道数和主用户数不变，运行30次算法取均值网络效益的仿真结果。由图5可知，随着认知用户数的不断增加，网络效益逐渐减小，主要原因就是当可用信道数为一个不变的值时，认知用户数逐渐增加，信道资源开始处于紧张状态，进而分配不足导致获取的效益减小。

图6为在可用信道数和认知用户数固定的情况下，其他参数都按照条件默认值设置，独立运行20次的试验次数与认知用户接入公平性的曲线。由图可知，ISSA具有最大的网络公平性，优于其他算法，也反映了ISSA算法的有效性。

图6 试验次数认知用户数接入公平性关系曲线

5 结束语

为解决认知无线电中频谱分配过程存在的优化问题，文中提出了一种改进的ISSA算法，并将其应用到认知无线电频谱分配中。通过使用透镜成像反向学习策略来增加麻雀种群的多样性，同时引入飞行策略控制麻雀转移步长，来提高算法在求解寻优问题过程中的收敛速度与精度。通过与原始麻雀搜索算法(SSA)、遗传算法(GA)、粒子群算法(PSO)、海鸥算法(SOA)进行对比测试，表明改进算法后的网络系统性能得到了明显的改善，表现出更快的收敛速度，一定程度上提高了认知用户的接入公平性。下一步将对认知无线电在干扰条件下的频谱分配和频谱的动态分配进行研究。