基于统计特性的蝙蝠算法在认知无线电频谱分配中的应用

朱冰莲, 朱文勇, 朱志青, 陈 玲, 刘紫娟

(1. 重庆大学通信工程学院, 重庆 400044; 2. 重庆大学通信与测控中心, 重庆 400044)

0 引 言

认知无线电技术是解决频谱供需矛盾的有效方法,被视为未来无线通信技术的核心技术之一[1]。频谱分配是认知无线电中的重要技术,其目标是将主用户未使用的空闲频谱分配给次用户,以提高频谱资源利用率,实现最大化频谱效益。

频谱分配影响着频谱资源的利用率,因此各类频谱分配模型相继被提出,包括图论模型[2-3]、拍卖模型[4]和博弈论模型[5]等。图论模型通过选择不同的目标效用函数能够满足不同应用场景的需求,很快成为研究热点。图论模型由文献[3]提出,被证明是一个典型的NP-Hard带约束条件的组合优化问题。文献[3]采用图着色算法进行寻优,分析了该模型下的网络总效益和用户公平性。图着色算法求解速度快但检测结果差[6]。文献[7]对该模型的解编码进行了压缩编码[7],随后,遗传算法(genetic algorithm, GA)、二进制粒子群算法(binary particle swarm optimization, BPSO)[8]、离散人工蜂群算法(discrete artificial bee colony, DABC)[9-10]等智能算法被引入到该问题的求解,取得了较好的效果。但当问题规模加大时,这些算法的收敛性能受到严重挑战。寻找高效的新型启发式优化算法解决该问题成为必然趋势。

蝙蝠算法[11]是Yang于2010年提出一种全局最优搜索算法,该算法结构简单、收敛性能好,已被成功应用于各类工程实际问题[12-13]。但蝙蝠算法在连续域提出,不能直接应用于离散问题的优化。为了进一步拓展蝙蝠算法在实际工程中的应用,本文将蝙蝠算法应用到频谱分配优化中,对蝙蝠算法进行离散化处理,并针对优化问题进行改进,取得了更好的效果。

1 蝙蝠算法

1.1 标准蝙蝠算法

蝙蝠是一种非常有趣的动物,有着先进的回声定位能力。其在空中飞行或搜寻猎物时,会使用一种叫做回音定位的声波定位器来捕捉猎物和躲避障碍物。蝙蝠一旦发现猎物,就会逐渐减小脉冲音量,增大脉冲发生率,以便于跟踪猎物,直到将其捕获。蝙蝠算法是一种模拟蝙蝠捕获猎物的行为来优化工程项目中目标函数的智能算法[12]。

标准蝙蝠算法[11]中,用蝙蝠的位置表示待优化问题的解,每个蝙蝠对猎物进行搜索时有着以下动作:

(1) 所有蝙蝠利用回声定位的方法感知距离,并可判断猎物和障碍之间的不同。

(2) 第i只蝙蝠的飞行速度为vi,发出超声波的频率为fi(或波长λ),其音量(振幅)为Ai来搜寻猎物。同时,蝙蝠根据自身与目标的距离自动调整发出脉冲的频率(或波长)和脉冲发生率ri。

(1)

(2)

(3)

xnew=x*+εAt

(4)

式中,ε为[-1,1]的随机数向量;At为种群中所有蝙蝠在同一时刻音量的平均值。随着Ai的减小,开发能力增强,蝙蝠位置(解)精度提高。

蝙蝠的速度和位置更新步骤有些类似于标准粒子群算法,如fi本质上控制了聚焦粒子运动的节奏和范围。在某种程度上,蝙蝠算法可看做标准粒子群优化以及强化局部搜索算法的结合,音量和脉冲发生率控制着其探索能力和开发能力。当蝙蝠寻找到猎物时,它的音量就会降低,同时脉冲发生率增加。两者更新为

(5)

(6)

1.2 二进制蝙蝠算法

蝙蝠算法初期提出主要用来解决连续空间函数优化问题，为了解决实际工程中许多的组合优化问题,需要对原始蝙蝠算法进行离散化处理。一般采用Sigmoid函数法进行离散化。在二进制蝙蝠算法(binary bat algorithm, BBA)[14]中,蝙蝠的每一维位置都限定为二进制0或1,但其速度大小没有被限制,从而利用速度的大小来确定其在对应位置上是0或1,即位置更新意味着从0和1之间的相互转换。这里采用S型函数进行离散化,蝙蝠位置更新为

(7)

(8)

综上所述,BBA算法流程如下:

步骤1初始化蝙蝠种群,随机产生蝙蝠的位置xi和速度vi。

步骤3根据式(1)调整频率,根据式(2)更新蝙蝠的速度。

步骤4产生一个随机数rand,如果rand>ri,则根据式(4)生成新解。否则,根据式(3)生成新解。按式(7)和式(8)对新解进行离散化。

步骤5产生一个随机数rand,如果randF(x*),则接受新解,并增加ri,减小音量Ai,否则保持不变,其中F为待优化问题的函数。

步骤6根据蝙蝠位置,计算所有蝙蝠的适应度值,更新当前最优解x*。

步骤7如果达到所设置的最大迭代次数,停止执行算法;否则,转至步骤3。

1.3 基于统计特性的蝙蝠算法

经过离散化处理后的BBA可以应用到频谱分配优化问题中,但取得的效果并不好。因此,针对频谱分配的特点对蝙蝠算法进行改进,以得到更好的效果。根据BBA流程的步骤5,可以看出蝙蝠算法是非贪婪选择,这对于连续域优化问题,可以减少陷入局部最优的概率。由于频谱分配优化问题是一个NP-Hard问题,其解空间为有限可列,若采用贪婪选择,则可以增加算法在当前位置的开发能力。因此,本文采用贪婪选择策略,即只要新解比当前位置好,就接受该解。

除此之外,蝙蝠算法的局部开发能力有待于改进[15],在局部搜索时,应当考虑种群中其他蝙蝠的位置。受量子粒子群算法[16]启发,将平均最好位置作为蝙蝠算法位置更新的一种策略,提出基于统计特性的蝙蝠算法(bat algorithm based on statistical characteristics, SCBA)。在SCBA中,记录种群中各蝙蝠所经历的最好位置,利用统计分析方法,统计所有蝙蝠经历最好位置的分布情况,利用平均最好位置指导蝙蝠寻优。平均最好位置的定义为

(9)

对于一个种群大小NP=4,待优化问题维数D=5的二进制优化问题中,xt表示第t次迭代后各蝙蝠所经历的最好位置,由式(9)得到平均最好位置如图1所示。

图1 平均最好位置的定义Fig.1 Definition of mean best position

(10)

2 基于蝙蝠算法的频谱分配

由于图论模型参数简单,并且每个参数有着实际的物理意义,易于仿真实现。通过选择不同的目标效用函数能够满足不同应用场景的需求,很快成为频谱分配的研究热点,因此,本文选择图论模型。

2.1 图论频谱分配模型

假设通信环境改变的时长与频谱分配所需时间相比(主用户的位置变化、可用频谱数变化所需时间与频谱分配计算时间相比),可忽略不计。将用户之间的频谱使用情况用图表示,则可以利用无向图优化得到较优频谱分配方案。对于次用户数为N，可用频谱数为M的频谱环境,图论模型下的频谱分配的定义如下[3]:

定义1频谱可用性矩阵L。L={ln,m|ln,m∈{0,1}}N×M,其中,ln,m=1表示在该时刻用户n可利用频谱m进行通信,ln,m=0则表示在该时刻用户n不能用频谱m进行通信。

通过频谱感知技术可以检测到次用户在当前环境中可利用的频谱,将所有次用户和可用频谱的关系用矩阵L描述。

定义2频谱效益矩阵B。B={bn,m}N×M,其中,bn,m表示用户n使用频谱m能获得的最大带宽或吞吐量,具体到本文选择的是一个度量值。

由于次用户与认知基站的距离不同,可能采用不同的发射功率和调制技术,从而不同次用户使用相同的频谱,所获得带宽或传输速率也不同,用矩阵B描述各次用户在不同频段通信时的系统效益。

定义3干扰约束矩阵C。C={cn,k,m|cn,k,m∈{0,1}}N×N×M。其中,cn,k,m=1表示次用户n和k同时使用频谱m进行传输数据时,将会产生通信干扰。

次用户与次用户之间的距离和调制技术等因素,使得多个次用户使用同一频谱时,可能会产生通信干扰。用矩阵C描述当前环境中各次用户使用相同频谱时的干扰约束情况。

定义4无干扰分配矩阵A。A={an,m|an,m∈{0,1},an,m≤ln,m}N×M。其中,an,m=1表示该时段次用户n分配到频谱m。为了保证通信可行性与可靠性,必须保证分配矩阵A与干扰约束矩阵C不能冲突,即:当cn,k,m=1时,对任意n,k≤N,m≤M有an,m+ak,m≤1。

定义5用户效益值R。R={βn}N×1。其中,βn表示在分配矩阵A下,次用户n所获得效益值,计算为

(11)

定义6系统效益函数U(R)。用来评价频谱分配策略对系统效益影响的函数,其定义为

(12)

基于以上定义,从系统总效益的角度出发,求解无干扰频谱分配矩阵,使得当前认知无线电系统下用户所获得的系统总效益最大,其表达式为

(13)

2.2 基于统计特性的蝙蝠算法的频谱分配描述

本文提出SCBA算法的认知无线电频谱分配方案中,每只蝙蝠的位置对应一种频谱分配方案。因此,频谱分配问题的最终求解目标即为最大化系统效益的无干扰分配矩阵A。直接编码A,则其维数为N×M,当网络中次用户数N、可用频谱数M增加时,问题规模随着维数成指数级增长。由于可用性矩阵L对无干扰分配矩阵A的约束,即ln,m=0时,表示当前通信环境下用户n不能使用频谱m,从而频谱m不能分配给用户n使用,从而an,m只能为0。因此,文献[7,17]提出只对矩阵L中元素值为1的位置进行编码。此时,解的编码长度D根据矩阵L中非零元素的个数确定,其计算式为

(14)

如图2所示,在该认知无线电系统中,用户数N=5、频谱数M=4,通过频谱检测得到可用矩阵L,按照逐行的顺序抽取矩阵L中对应位置为1的元素,然后对它们进行编码,得到解向量x(xi∈{0,1}),其维数为8,优化以后,再按照之前的映射关系将解向量x映射为分配矩阵A。

图2 解向量与分配矩阵的映射关系Fig.2 Relationship between solution vector and allocation matrix

按照上述编码方式,随机的初始化蝙蝠位置(频谱分配方案),并不一定能满足定义3的无干扰约束条件。因此,需要对蝙蝠的位置进行干扰约束处理。对任意频谱m(0≤m

综上所述,本文提出的SCBA算法的认知无线电频谱分配流程如下:

步骤2初始化种群xi(i=1,2,…,NP),初始化速度vi、频率fi及脉冲发生率r。

步骤3干扰约束处理,将解向量xi还原成分配矩阵A,在干扰约束矩阵C中,对所有m(0≤m

步骤4根据式(1)调整频率,根据式(2)更新蝙蝠的速度。

步骤5产生一个随机数rand,如果rand>r,则利用平均最好位置指导蝙蝠寻优,按式(9)和式(10)更新蝙蝠位置,否则按式(3)更新位置,并按式(7)和式(8)进行离散化处理。

步骤6按照步骤3,对新解进行干扰约束处理。

步骤7计算蝙蝠适应度值,利用贪婪选择策略选择当前较好的蝙蝠进行下一次的迭代,并更新当前最优解。

步骤8若达到算法所设置的最大迭代次数,则算法结束;否则,转至步骤4。

2.3 算法复杂度分析

SCBA算法的计算时间复杂度即为种群迭代的时间复杂度。在执行种群迭代阶段,每只蝙蝠以概率r执行全局搜索,其复杂度为O(r·NP·2D),以概率(1-r)执行局部搜索,执行局部搜索操作的复杂度为O((1-r)·NP·D)),由此可得迭代一次的计算时间复杂度为O(r·NP·2D+(1-r)·NP·D),即O((1+r)NP·D),因此SCBA算法的计算时间复杂度为O((1+r)T·NP·D)。其中,T为算法迭代的最大次数。根据BBA算法流程可得其计算时间复杂度为O(2T·NP·D)。所以，SCBA算法的时间复杂度低于BBA算法的时间复杂度。

SCBA算法的空间复杂度主要包括频谱分配模型矩阵的存储和蝙蝠种群位置的存储。L所需的存储空间为O(N·M),B的存储空间为O(N·M),C的复杂度为O(N2·M)。每个蝙蝠位置的存储空间为O(D)。因此,在图论模型下SCBA算法的空间复杂度为O(N·M·(N+2)+NP·D),与其他算法的空间复杂度相同。

3 仿真实验及结果分析

根据文献[7-8,10,17],GA、BPSO、DABC、多策略离散人工蜂群算法(multi-strategy discrete artificial bee colony, MDABC)都应用于认知无线电频谱分配,在求解使得系统效益最大化的频谱分配方案中,MDABC的性能最好,其次分别是DABC、BPSO、GA。为了验证SCBA算法在认知无线电频谱分配中的有效性,与BBA和MDABC算法在同一条件下进行仿真测试。

假设认知无线电网络模型中次用户的个数为20,可用频谱数为22,即N=20,M=22。优化问题的维数D由式(14)计算。MDABC算法参数[17]为S=20,T1=[0.08D],U=SD;BBA和SCBA算法的参数:种群大小NP=20,音量A=0.6,脉冲发生率r=0.7；所有算法最大迭代次数为T=500。为了降低算法的偶然性,所有结果为各算法在同一条件下运行30次的平均值。

3.1 几种智能算法的比较

图3是3种算法在不同频谱环境下的系统总效益的平均值对比。该试验采用了30种不同的L、B、C矩阵,对于每种算法均采用相同的初始值。可以看出,SCBA算法在不同的频谱环境下都能使系统获得更大的效益值。

图4是在一次仿真实验中,系统效益与迭代次数的关系。从图中可以看出,SCBA的收敛速度快于MDABC和BBA两种算法,且在相同迭代次数时,寻找的频谱分配方案总使得系统获得更大的效益值。

图3 不同频谱环境下的系统效益值Fig.3 Benefit value of system in different spectrum environment

图4 不同算法下系统效益与迭代次数的关系Fig.4 Relationship between benefit value of system and iteration times under different algorithms

3.2 计算时间分析

图论模型下的频谱分配是基于某一短暂时间内频谱环境参数不变,对频谱进行分配,使系统效益最大化。以时间为横轴,效益值为纵轴,BBA、SCBA、MDABC算法在同一频谱环境下重复30次取平均值,得到平均计算时间与系统效益曲线如图5所示。

图5 系统效益与搜索时间的关系Fig.5 Relationship between benefit value and search time

从图5中可以看出,MDABC在迭代500次所需总时间少于BBA和SCBA,但所得频谱分配方案使得系统效益小于SCBA,且SCBA在0.8 s左右就收敛了。当使得系统效益相同时,SCBA所需时间更少。

3.3 系统效益随用户数和可用频谱数变化的关系

在认知无线电系统中,由于次用户数和可用频谱数受到主用户频谱使用情况、地理位置、发射功率大小等因素的影响和限制,其在不断地变化,从而影响整个系统的效益。图6为用户数固定为20,频谱数M从15变化到40时,系统平均效益(系统总效益与用户数之比)与可用频谱数之间的关系,从图中可以看出,当可用频谱数增加时,系统平均效益也增加,但是SCBA获得的用户平均效益略高于MDABC。

图6 系统平均效益与可用频谱数变化的关系Fig.6 Relationship between the average benefit value of system and the number of available spectrum

图7为频谱数M固定为30,用户数N从15到40变化时系统平均效益与用户数的关系仿真结果。从图中可以看出,用户数增加后,相互干扰的概率增加,用户获得的平均效益逐渐减小。但是,SCBA获得的系统平均效益高于BBA和MDABC。

图7 系统平均效益与用户数变化的关系Fig.7 Relationship between the average benefit value of system and the number of users

4 结 论

本文提出了改进蝙蝠算法的认知无线电频谱分配方法。①将蝙蝠算法的选择策略改为贪婪选择,增强了蝙蝠算法在当前位置的开发能力,提高了解的精确性。②根据蝙蝠种群中位置的统计特性,即,平均最好位置反映了所有蝙蝠在该位置上取0或1的趋势,根据这一趋势,在下一次迭代中产生更好的解,加快算法收敛速度。③在局部搜索时,直接在离散域操作,减少实数到二进制的映射,从而缩短搜索时间。通过仿真比较了BBA、SCBA和MDABC在频谱分配中的应用,仿真结果表明,SCBA获得的频谱分配方案与BBA和MDABC相比,系统效益更大,且所需时间更少。

[1] AKYILDIZ I F, LEE W, VURAN M C, et al. Next generation/dynamic spectrum access/cognitive radio wireless networks: a survey[J]. Computer Networks, 2006, 50(13): 2127-2159.

[2] LIU Q, NIU H, XU W, et al. A service-oriented spectrum allocation algorithm using enhanced PSO for cognitive wireless networks[J]. Computer Networks, 2014, 74:81-91.

[3] PENG C Y, ZHENG H T, ZHAO B Y. Utilization and fairness in spectrum assignment for opportunistic spectrum access[J]. Mobile Networks and Applications, 2006, 11(4): 555-576.

[4] LI Z P, LI B C, ZHU Y F. Designing truthful spectrum auctions for multi-hop secondary networks[J]. IEEE Trans.on Mobile Computing, 2015, 14(2): 316-327.

[5] ZAYEN B, HAYAR A, NOUBIR G. Game theory-based resource management strategy for cognitive radio networks[J]. Multimedia Tools and Applications, 2014, 70(3): 2063-2083.

[6] 高洪元,曹金龙. 认知无线电中的量子蛙跳频谱分配[J]. 应用科学学报, 2014, 32(1): 19-26.

GAO H Y, CAO J L. Quantum-inspired shuffled frog leaping algorithm for spectrum allocation in cognitive radio[J]. Journal of Applied Sciences, 2014, 32(1):19-26.

[7] ZHAO Z J, PENG Z, ZHENG S L, et al. Cognitive radio spectrum allocation using evolutionary algorithms[J]. IEEE Trans.on Wireless Communications, 2009, 8(9): 4421-4425.

[8] 赵知劲, 徐世宇, 郑仕链, 等. 基于二进制粒子群算法的认知无线电决策引擎[J]. 物理学报, 2009, 58(7):5118-5125.

ZHAO Z J, XU S Y, ZHENG S L, et al. Cognitive radio decision engine based on binary particle swarm optimization[J]. Acta Physica Sinica, 2009, 58(7):5118-5125.

[9] GHASEMI A, MASNADI-SHIRAZI M A, BIGUESH M, et al. Spectrum allocation based on artificial bee colony in cognitive radio networks[C]∥Proc.of the 6th International Symposium on Telecommunications, 2012:182-187.

[10] 李鑫滨,刘磊,马锴. 基于离散人工蜂群算法的认知无线电频谱分配[J]. 系统工程与电子技术. 2012, 34(10): 2136-2141.

LI X B, LIU L, MA K. Cognitive radio spectrum allocation based on discrete artificial bee colony algorithm[J]. Systems Engineering and Electronics, 2012, 34(10):2136-2141.

[11] YANG X S. A new metaheuristic bat-inspired algorithm[M]. Nature Inspired Cooperative Strategies for Optimization. Berlin Heidelberg: Springer, 2010:65-74.

[12] YE Z, WANG M, LIU W, et al. Fuzzy entropy based optimal thresholding using bat algorithm[J]. Applied Soft Computing. 2015, 31(0): 381-395.

[13] YANG X, GANDOMI A. Bat algorithm: a novel approach for global engineering optimization[J]. Engineering Computations, 2012, 29(5): 464-483.

[14] MIRJALILI S, MIRJALILI S M, YANG X S. Binary bat algorithm[J]. Neural Computing and Applications, 2014, 25(3):663-681.

[15] YILMAZ S, UGUR KUCUKSILLE E, CENGIZ Y. Modified bat algorithm[J]. Elektronika Ir Elektrotechnika, 2014, 20(2):71-78.

[16] SUN J, FANG W, PALADE V, et al. Quantum-behaved particle swarm optimization with Gaussian distributed local attractor point[J].Applied Mathematics and Computation, 2011,218(7): 3763-3775.

[17] 朱冰莲,朱方方,段青言,等.采用多策略离散人工蜂群的改进频谱分配算法[J].西安交通大学学报,2016,50(2):20-25.

ZHU B L, ZHU F F, DUAN Q Y, et al. An improved spectrum allocation algorithm using multi-strategy discrete artificial bee colony technology[J].Journal of Xi’an Jiaotong University, 2016,50(2):20-251.