基于混沌二进制粒子群算法的认知无线电频谱分配策略

滕志军，谢露莹，滕利鑫，曲福娟

(1.现代电力系统仿真控制与绿色电能新技术教育部重点实验室,吉林 吉林 132012；2.东北电力大学 电气工程学院, 吉林 吉林 132012)

0 引 言

随着无线电通信技术的迅猛发展，以超高速，超高容量，超短时延著称的5G技术在未来几年内即将商业化，无线通信业务量将大幅度增加[1-2]。因频谱资源紧张和频谱分配方式的缺陷造成的频谱利用率低与通信业务需求间的供需不平衡问题日益严峻，认知无线电可动态探测无线环境，通过智能算法和自主学习技术更新数据，同时可进行空闲频谱判断与发射和接收机的工作参数校正调整，实现灵活接入频谱空穴。到目前为止，已将图论着色模型[3]，博弈论模型[4]，定价拍卖模型[5]等经典数学模型及人工智能算法与认知无线电技术相结合，以其优越性能优化频谱分配问题[6-7]。

文献[3]考虑用户实际通信过程中需求的带宽不同，设计基于用户优先级函数的改进CSGC算法进行二次频谱分配，该算法有效提高了频谱利用率但获得的网络效益较低且实现过程较复杂。文献[8]利用混沌映射优化初始种群，量子旋转门筛选克隆变异个体，改进传统克隆算法求解多目标频谱分配问题，该算法将混沌映射、量子学和克隆算法结合，得到较高的性能精度，但计算过程较复杂且计算时间较长。文献[9]在二进制粒子群算法上设计约束算子，将使用频谱相互干扰的用户进行约束，将改进后算法进行频谱分配应用验证，该算法可保障认知用户间公平占用频谱，但二进制粒子群算法后期搜索方向单一且收敛慢，使得分配方案仍有不足。文献[10]设计一种基于改进二进制粒子群算法(improved binary particle swarm optimization，IBPSO)的频谱分配方案，该方案对粒子速度公式进行离散化改进，以改进后公式更新粒子位置，保证了进化的连续性，但算法同样难以得到理想解。文献[11]提出基于种群聚集度的二进制粒子群算法的频谱分配方案，改善了原始算法不易寻找全局最优解的缺陷和易早熟的问题，但并未考虑可用频谱数量与算法全局寻优的关系，降低算法的普适性。

针对现有改进的CSGC算法和改进的二进制粒子群算法在频谱分配过程中所出现的计算复杂、收敛迭代次数多、易得到部分最优现象等问题，本文设计降维频谱排序列表的频谱分配方案，提出混沌二进制粒子群算法(chaos logistic binary particle swarm optimization，CLBPSO)。引用具有遍历性优势的混沌映射，映射初始种群的粒子位置及后期粒子的速度，减少计算复杂度，改善初始种群以提高后期搜索能力，获得全局理想解。仿真实验证明，与图论算法(color sensitive graph coloring，CSGC)和改进二进制粒子群算法相比较，本文算法收敛速度快，可获得更高系统收益。

1 频谱分配模型

在认知无线电系统中，主用户(primary user, PU)和次用户(secondary user, SU)通过改变发射功率调整通信范围，通信范围为大小不等的圆，如图1。图1系统模型中有3个PU，6个SU和3个可用信道，可用信道数与主用户数相同。在PU通信范围内的SU不能使用该PU用户占用的信道，以保证SU在占用信道时不会影响PU的正常工作，即图中的SU1，SU2不能使用PU1占用的信道A，在PU1通信范围外的SU3，SU4，SU5，SU6可以占用信道A。其他信道的可使用情况以此类推。还需注意的是图中SU3和SU4两者的通信范围有交叠，说明两者不能同时使用相同信道，否则会产生通信干扰。

图1 认知无线电系统模型Fig.1 Cognitive radio system model

本文的频谱分配模型采用经典的图论着色模型，用N，M分别表示认知用户集合和可用频谱集合，可用矩阵L、效益矩阵B、干扰矩阵C和无干扰分配矩阵A描述为[12]

1)可用矩阵L为

L={ln,m|ln,m∈{0，1}}N×M

(1)

(1)式中，ln,m为认知用户n对信道m的使用关系，若ln,m=1，表示认知用户n可以使用频谱m；ln,m=0，则表示认知用户不可以使用频谱m。

2)效益矩阵B为

B={bn,m|bn,m>0}N×M

(2)

(2)式中，bn,m为次级用户n占用相应信道m时可得到的带宽效益大小，单位为KB/s。由于位置不同的次级用户发射和调制的方式会不同，所以各用户获得的效益有所差异，当ln,m=0时，bn,m=0。

3)干扰矩阵C为

C={cn,k,m|cn,k,m∈{0，1}}N×N×M

(3)

(3)式中，cn,k,m为多个次级用户使用同一信道的干扰关系，若cn,k,m=1，则认知用户n，k使用信道m的时候会产生干扰，不可以同时占用，反之，可以同时使用，并且C由L决定，即cn,k,m≤ln,m×lk,m，当n=k时，cn,n,m=1-ln,m。

4)无干扰分配矩阵A为

A={an,m|an,m∈{0，1}}N×M

(4)

(4)式中，an,m为各个认知用户可能分配到的一种有效频谱情况，若an,m=1，表示认知用户n分配到了频谱m，反之，表示认知用户n没有分配到频谱m。认知用户占用的频谱必须对其他用户无影响，即满足约束规则：an,m+ak,m≤1和cn,k,m=1，∀n，k∈[1，N]，m∈[1，M]。

本文主要以网络效益为衡量指标，表示为

(5)

(6)

(5)式表示系统网络效益的总和，其中，αn为单个用户n的总效益；(6)式中Λ(L,C)N,M为符合约束条件的所有可用频谱矩阵解集，即A的集合。本文要实现的工作就是根据(6)式的目标函数找到最优的分配矩阵A*。

2 混沌二进制粒子群算法

2.1 标准二进制粒子群算法

粒子群算法只能在连续空间搜寻，但在离散空间无法实现搜索迭代，为解决此缺陷，二进制粒子群被提出[13]。由于频谱分配是在二进制空间进行处理的，所以可以应用此算法寻找最优方案。

在二进制粒子群算法中，每个微粒的取值为二进制数值，即取0或1。微粒速度和位置更新可以分别表示为

(7)

(8)

(9)

2.2 粒子位置和速度的混沌映射优化

粒子群算法在初始化种群过程中产生的粒子是在解空间中随机分布的，初始化种群的好坏会对后期迭代运算的结果产生一定影响。为此在种群初始化时期引入混沌映射，利用其全局遍历性和初值敏感性[15]，将初始种群粒子均匀全局分布在解空间，便于粒子更好地全局寻优，找到初始全局最优解。二进制粒子群算法在后期算法迭代搜索过程中易陷入局部最优，因此对每代粒子速度进行混沌优化，使粒子在搜索迭代中通过进化逼近全局最优。

本文采用Logistic映射来生成混沌变量，可以表示为

ys+1=μys(1-ys)

(10)

(10)式中：ys为第s次迭代产生的粒子位置优化的混沌变量，ys∈[0，1]；μ作为控制遍历状态的参数，当μ=4，变量会遍历到整个搜索空间[15]，即为混沌空间[0,1]的所有状态。为确保混沌序列元素的值域为[0,1]，使其符合频谱分配二进制编码方式，本文在文献[16]工作基础上引入取整函数，对混沌映射后的变量进行修正，省掉二进制编译码的工作量，节省计算时间。修正公式为

xi=round(ys+1)

(11)

(11)式中：round()算子为取整函数；xi是修正后的粒子位置变量。在每次迭代更新速度过程中进行混沌映射时，需实现混沌空间和变量空间之间的转化[16]，转化的过程需要映射和逆映射实现，分别表示为

(12)

(13)

3 基于混沌二进制粒子群算法的频谱分配策略

本文要解决的是将频谱分配问题映射为二进制混沌粒子群算法中粒子的寻优问题。二进制混沌粒子群算法中粒子主要包含位置和速度2个变量，利用混沌映射迭代优化粒子的位置和粒子的速度。粒子的位置代表一种可行的频谱分配方案，粒子的速度则是更新优化位置的依据，粒子通过迭代更新变换从而寻找到最优方案。把最大化网络效益作为粒子搜寻函数，评价粒子寻优解好坏，求解最高效的分配频谱方案的依据。

3.1 算法流程

算法随机初始化粒子种群位置和速度变量，利用混沌映射的随机遍历性优化初始粒子位置，使粒子遍历初始解空间提高初始粒子全局搜索性。计算优化后粒子群的适应函数值，评选pbest和gbest。粒子速度在本文中代表搜索步长，为避免粒子陷入局部最优搜索遗漏可能最优解，同样对粒子的速度进行混沌优化，通过映射和逆映射实现。以粒子速度为依据更新粒子位置，评价每代粒子信息，循环迭代直到达到最大迭代次数，算法停止运行。算法具体实现流程如图2。

图2 算法流程图Fig.2 Flow chart of algorithm

3.2 关键技术

3.2.1 频谱编码映射

本文基于图论模型进行频谱分配，故分配问题等同0-1规划问题，可采用二进制编码方式，1代表信道可使用，0代表信道不可使用。对于单个授权网络，假设共享信道数量少，且认知用户数N大于共享信道数M。基于此分析为N个不同用户高效分配M个共享频谱，由于L中0元素对应的m不可被指定的n使用，因此只需将L中1元素所表示的频谱进行种群编码，即粒子维数由L中1的取值数q确定，粒子位置每一维取值为0或1，每个粒子的位置代表一种分配方案，相应的可行分配方案一共有F=2q-1种。L和粒子位置X之间的对应编码映射关系如图3所示，L为N=4，M=3时的可用矩阵，X为粒子的位置解。

图3矩阵L和粒子位置X的编码映射
Fig.3CodingmappingofmatrixLandparticlelocationX

3.2.2 粒子修正

粒子在更新迭代位置时，会产生不满足无干扰约束条件和频谱可用条件的位置，需要对这种粒子位置进行无干扰约束修正处理。首先，根据图3编码映射方式将粒子位置的解映射到无干扰分配矩阵A中；然后对任意的m寻找所有满足cn,k,m=1且n≠k的情况，检查A中m列中n行和k行上的状态量值是否均为1，若是1，则随机更改其中一个元素为0，另一个保持不变。修改后的矩阵A为新的可行解。

3.2.3 降维频谱分配列表D

频谱编码将搜索空间由N×M维降到q维，以缩小搜索空间和减少算法的搜索时间开销。但q维可用频谱分配有F=2q-1种搜索方式，为使算法在搜索过程中快捷高效寻找最优频谱方案，故建立降维频谱分配列表D。

定义D=[D1,…,Df,…,DF]T，表示认知用户搜寻频谱分配方案的所有可能情况列表。其中Df=[d1,d2,…,dq]，F是可行的频谱方案总数，f是频谱分配方案标号，q是可进行频谱分配的频谱数，dq∈{0，1}，(d1,d2,…,dq)以二进制方式有序排列。

3.3 混沌二进制粒子群算法求解频谱分配步骤

1)初始化算法参数包含(7)式中c1，c2，w，种群最大迭代次数T，粒子种群个体数E及(10)式混沌迭代次数S。

3)计算初始粒子群的适应函数值，将(5)式作为适应度函数，选出个体的最大值pbest和种群最大值gbest，保存初代粒子最大的适应函数值，同时保存粒子位置及最优的频谱分配方案。

4)更新每个粒子的速度vi，由于粒子的速度vi表示搜索频谱方案列表的步长，粒子的位置xi表示频谱分配方案列表中的一种可行方案，因此需要在(7)式的基础上进行调整变换。调整后的表达式为

(14)

5)根据(8)—(9)式更新每个粒子的位置xi。

7)如果达到最大迭代次数T，则算法结束，得到最优的频谱分配方案gbest；否则，跳到步骤3)继续循环迭代更新。

3.4 算法复杂性分析

算法实现的复杂性主要包括用户分配模型运算和算法迭代运算。将本文算法与CSGC算法和IBPSO算法进行运算复杂度对比分析如表1。本文定义了降维频谱分配列表将用户分配模型由N×M维降到q维，故CLBPSO算法的用户分配模型运算复杂度为O(q)，小于IBPSO算法和CSGC算法的用户分配模型的运算复杂度O(N×M)。由于CSGC算法的运算只与用户数和信道数有关，所以，3种算法运算复杂度分别表示为O(q×T×POP×D)，O(N×M×T×POP×D)，O((N×M)2)，其中，T代表算法迭代次数，POP代表种群规模，D代表粒子维数，N代表认知用户数，M代表信道数。T，POP，D都为定值常数，由算法复杂度关系可知，O(N×M)

表1 算法实现复杂度比较

4 实验仿真与分析

为验证本文CLBPSO算法在分配频谱过程中的有效性，以网络效益总和为准则，在Matlab R2012a编程环境下，将本文算法与经典CSGC算法和IBPSO算法加以对比。

4.1 仿真场景参数设置

具体仿真场景参数设置如表2。

表2 仿真参数设置

4.2 算法参数设置

算法参数设置如表3，c1，c2，w的取值为PSO算法的标准值，混沌控制权值μ取值确保了完全混沌状态，种群规模E、算法最大迭代次数T和混沌映射次数S取值与模拟系统有关。

表3 算法参数设置

4.3 仿真结果及分析

图4是在频谱数M和认知用户数N同为5，3种算法在不同迭代次数下所获得的网络效益总和变化图。由图4可知，本文CLBPSO算法在50，100，200次迭代时获得网络效益总和值分别为113.84，121.89，122.97，均高于CSGC算法和IBPSO算法所获得的网络效益。对网络效益总和的目标函数来说，CLBPSO算法得到了较理想的全局网络效益总和，较IBPSO算法网络效益总和提高了3.74%，这是因为后期粒子寻优与混沌映射的结合重新将粒子遍历搜索空间，使得粒子跳出局部搜索进而实现全局寻优，得到较理想的全局解。从各算法整体性能来看，CSGC算法收敛最快，是由于CSGC算法进入部分最优，但所获网络效益最低。综上分析，与CSGC算法和IBPSO算法相比，CLBPSO算法获得了较理想全局最优解。

图4 不同算法迭代次数下获得的网络效益Fig.4 Network award of different algorithms iteration times

当认知用户数与频谱数相等都为5时，进行50次仿真实验，以比较3种算法在最大化网络效益总和下的性能优劣，仿真结果如图5。在50个实验样本中，CLBPSO算法获得的网络效益明显高于其他2种算法，证明CLBPSO算法可获得理想的网络收益。

当认知用户数N=20固定不变，频谱数M由5递增到25时，进行100次实验，可用频谱对算法所获效益影响如图6。在认知用户数不变频谱数目递增的情况下，网络总效益随之增加，且CLBPSO算法与另2种算法相比网络效益增加的幅度较大。由于CLBPSO算法从初始种群到后期搜索均采用混沌映射，遍历所有可能分配情况，找到较理想的最优解，收益最高，IBPSO算法收益其次，经典CSGC算法最低。CLBPSO算法较IBPSO算法收益提高15%左右。

图5 不同实验下算法所获网络效益总和Fig.5 Network sum award of different algorithm experiments

图6 可用频谱数对算法所获效益影响Fig.6 Award comparison of different algorithms versus available spectrums

当频谱数M=15固定不变，认知用户数N由5递增到25时，进行100次实验，认知用户数对算法所获效益影响如图7。在频谱数不变的情况下，认知用户数在递增的过程中网络总效益在递减，这是因为多认知用户竞争少量资源的结果。在网络效益减少的情况下，CLBPSO算法获得的网络收益依旧较高，IBPSO算法其次，经典CSGC算法最低。CLBPSO算法较IBPSO算法收益提高了10%左右，CLBPSO算法较优。

图7 认知用户数对算法所获效益影响Fig.7 Award comparison of different algorithms versus cognitive users

4.4 算法运算时间开销对比

表4是3种算法在计算时间上的开销比较。从表4可以看出，CLBPSO算法在Clock计算时间方式下计算的运行时间低于CSGC算法运行时间，高于IBPSO算法运行时间约0.688 s，高出的时间较小。CLBPSO算法在TIC和TOC计算时间方式下计算的运行时间最小。综合2种时间计算方式进行对比分析，CLBPSO算法的计算时间开销较低，较其他2种算法有优势。

表4 不同算法的收敛时间开销对比

5 结 论

本文在二进制粒子群算法基础上，引入混沌映射，将时变可用频谱建立成降维频谱分配数学模型，并以此为优化基础，对初始种群和粒子速度进行优化，提出混沌二进制粒子群算法，以网络总效益为算法衡量准则来验证其应用性能。仿真结果表明，混沌二进制粒子群算法可以获得较高网络收益，且收敛速率快、鲁棒性高。下一阶段将围绕评判w值与算法适应度之间的关系以提高算法收益和效率开展研究。