基于多态蚁群优化算法的认知无线电频谱分配

孙汉卿 刘 征 王桂芝 连卫民

(河南牧业经济学院信息工程学院 河南 郑州 450044)

0 引 言

近年来，无线通信领域持续繁荣，导致频谱资源严重紧缺。认知无线电(Cognitive Radio,CR)技术是解决此类问题的有效方式之一，它可以自动找寻并且充分利用可用的频谱资源[1]。在认知无线电网络中，认知用户可以接入频谱资源的前提条件是不能对主用户产生干扰，认知用户是以一种机会的方式占用可用频谱资源[2]。频谱分配的核心思想是对感知到的未被占用的频谱进行公平且高效的分配，从而提高频谱的使用效率[3]。频谱分配问题本质上是一种优化问题且具有非确定性特点，所以采用智能算法对频谱分配问题进行求解非常有效。蚁群算法的思想在解决全局优化求解问题中得到了广泛使用，无论是解决简单的单目标优化问题，还是复杂的多目标优化问题都非常有效。

目前，国内外研究人员针对认知无线电频谱分配的智能算法求解取得了一定研究成果。文献[4]提出了一种基于蚁群优化算法的认知无线电频谱分配方案，通过引入学习因子改良了信息素的积累方式，进一步缩短计算最优解的时间，有效节约了时间开销。但由于分配模型的效益函数不完善，使得该算法无法兼顾增益矩阵，导致网络总效益有所下降。文献[5]提出了一种基于遗传算法和蚁群算法相结合的频谱分配算法，通过遗传算法求出初始解，再利用衔接策略将初始解转化为蚁群算法所需的信息素，最终求得最优解。该算法虽然在一定程度上提高了网络平均效益，但未针对频谱分配的公平性问题进行讨论。文献[6]提出了一种基于感知时间和门限联合的频谱分配优化模型，通过采用“先听后传”的次用户帧结构，从频谱感知时间和子信道感知门限出发求得最优解，能确保系统拥有较高的吞吐量，但是其会导致认知用户之间的竞争增大，无法保证系统的公平性。文献[7]提出了一种改进蚁群算法的无线电频谱智能分配策略，该算法在传统蚁群算法的基础上，引入了自助查询搜索窗口，通过限定蚂蚁的前进路径来缩短搜索时间，从而达到提高网络系统整体效益的目的，但是该算法在整体寻优方面存在不足，不能很好地求得全局最优解。

综上可知，现有认知无线电频谱分配模型大都采用平均分配模式进行分配，并未从认知用户需求角度出发，仅根据差别用户对频谱的需求程度分配将导致公平性较低，频谱资源得不到较好利用[8-9]。为解决认知无线电频谱分配中认知用户间竞争大、网络效益低，以及认知用户接入可用频谱所用时间长等问题，本文给出一种基于多态蚁群优化算法的认知无线电频谱分配方案(cognitive radio spectrum allocation based on improved polymorphic ant colony algorithm,IPAC)。IPAC算法思想是：基于传统蚁群算法计算蚂蚁的转移概率，为蚂蚁的行动提供依据；针对传统蚁群算法未考虑蚂蚁到达节点的时间因素，引入一个时间因子生成新的信息素分配方法，并按照“蚂蚁达到节点的时间越少，所分配信息素越多”原则进行信息素分配，更加公平地分配信息素；对所有认知用户的信息素进行排序，将信道分配给信息素最大的认知用户。该算法可以较好地确保认知用户之间的公平性，大幅节省频谱分配所需时间，提高信道利用率，有效减少了认知用户的搜索时间，从而提高系统收敛速度、网络效益和吞吐量。

1 认知无线电频谱分配模型

认知无线电频谱分配基本模型[10]如下：在分布式认知无线电频谱共享系统模式下，认知用户(次用户)通过感知主用户(授权用户)信号的情况，在不干扰主用户接入频谱的前提下，根据其自身的性质、性能、方位等情况获得所需的可用频谱。每个认知用户通过这种方式获取各自的可用频谱，并了解有关受到的干扰约束条件，实现了认知用户之间的信息交互[12]。频谱共享的方式有以下两种：一是通过控制信道获取所需的信息；二是通过认知无线网络的基站获得频谱资源占用情况。认知无线电频谱分配主要采用可用频谱矩阵LN×M、干扰约束矩阵CN×K×M、信道效益矩阵BN×M和无冲突分配矩阵SN×M进行描述。其中：N表示认知用户的总数量，n表示N中的某个认知用户；M表示信道的总数量，m表示某个频谱；K表示另一认知用户的总数量，k表示K中的某个认知用户。下面对上述四种矩阵分别进行说明：

1)可用频谱矩阵LN×M。假如主用户已经占用频谱m，此时如果要使用该频谱将会对主用户的正常接入造成不必要的干扰。可用频谱矩阵仅用于主用户之间，不考虑认知用户之间的相互干扰。

2)干扰约束矩阵CN×K×M。该矩阵主要是用于说明不同认知用户之间的干扰约束问题。假如存在cn,k,m=1，则说明如果认知用户n和认知用户k同时占用同一信道m，将会使它们彼此之间的干扰增大。干扰约束条件主要取决于用户所在区域、用户间的距离和信号的强度三个因素。

3)信道效益矩阵BN×M。该矩阵主要是用于说明一个认知用户接入某个信道时所得到的信道吞吐量，即该用户是否顺利接入该频带。bn,m表示在没有邻道干扰的情况下，认知用户n接入频带m后，可获得的最大带宽吞吐量比。如果在可用频谱矩阵中ln,m=0，则有bn,m=0。

4)无冲突分配矩阵SN×M。若sn,m=1，则认知用户n此时正在使用频带m。若sn,m=0，则此时无法将频带m分配给认知用户n使用。同时，该矩阵需要满足LN×M和CN×K×M所规定的干扰约束条件。

2 基于蚁群算法的转移概率计算

2.1 相关参量设置和规则

基于蚁群算法的频谱分配方案转移概率计算相关参量设置和规则如下：

(1)节点：蚂蚁可能访问的每一个认知用户。

(2)移动路径：为认知用户分配的一个信道。

(3)蚂蚁个数：采用序号χ表示蚂蚁的个数。

(4)迭代次数：采用编号ξ表示迭代的次数。

(5)认知用户个数：蚂蚁访问的节点数量，总数量用N表示，编号用n表示。

(6)信道数量：信道总数量用M表示，编号用m表示。

(7)可用信道矩阵L：属于动态调节矩阵，根据每个蚂蚁位置变化自动调节数值。

(8)干扰约束矩阵C：属于动态调节矩阵，根据每个蚂蚁位置变化自动调节数值。

(9)信息素矩阵TN×M×ξ：矩阵中的元素表示蚂蚁在第ξ次迭代时第n个认知用户在第m个信道处释放的信息素多少，N表示认知用户的总个数，M表示信道的总数，ξ表示迭代的次数。

(10)规则1：每个认知用户均拥有相同数量的蚂蚁，即每个认知用户成为源节点的概率是相同的。

(11)规则2：蚂蚁走过的每个节点都进行记忆，且每只蚂蚁只能走过相同的节点一次，即每个节点不会被相同的蚂蚁重复经过。

上述(7)、(8)两条主要用于决定：① 蚂蚁经过节点时释放的信息素多少；② 当蚂蚁到达该节点时能获得的信道效益大小；③ 蚂蚁所经历路线的长短；④ 蚂蚁能否到达终点。

2.2 转移概率计算步骤

(1)

式中：Yn,m表示认知用户n在信道m上的消耗函数；K表示另一认知用户的总个数；cn,k,m为干扰约束矩阵CN×K×M中的元素，当cn,k,m=1时，认知用户n和认知用户k之间存在干扰，反之则不存在干扰；lk,m为可用频谱矩阵LN×M中的元素，当lk,m=1时则说明认知用户k也可以使用该信道，反之则说明该信道已被占用。

步骤2判断蚂蚁行为。蚂蚁行动函数Aχ,ξ决定蚂蚁的下一步行动，判断准则如下：

(2)

式中：χ表示蚂蚁个数；ξ表示迭代次数。当Aχ,ξ=0时，表示认知用户n使用信道m时对其他认知用户不造成干扰，此时蚂蚁会继续移动直到终点，否则蚂蚁χ继续留在该节点，不再前进；当Aχ,ξ=1时，蚂蚁前进寻找新的节点。

每当蚂蚁完成一次行动，开始下次行动之前，需要删除上一个节点分配的信道以及与其产生干扰的信道，同时重新设置节点与信道之间的干扰约束关系。随着蚂蚁行为的不断变化，认知用户的可用信道和干扰约束关系也会随之改变，可通过改变L和C的值来反映这种变化。

步骤3蚂蚁转移概率。蚂蚁行动未终止时需要根据转移概率选择下一节点，所以为了保证路径的多样性，蚂蚁的行动既要考虑信息素的大小，也要考虑观测值的大小。其中，观测值是与消耗及干扰相关的函数：

(3)

式中：Yn,m表示认知用户n在信道m上的消耗函数；DLn,m表示认知用户n使用信道m时的信道切换时延Dswitching,ln,m和排队等候时延Dqueueing,ln,m之和。

DLn,m=Dswitching,ln,m+Dqueueing,ln,m

(4)

切换时延是指节点n从前一信道h接入到信道m所产生的切换时延：

(5)

式中：f表示取值为0～1之间的调节因子，用于避免时延在观测值函数中所占比重过大；Timem表示节点n接入信道m的时间；Timeh,m表示从h信道开始向m信道转换的时间。

但如果次用户j可能正在使用信道m，则需要等待次用户j不再使用信道m后再接入，由此产生排队时延：

Dqueueing,ln,m=Timen,m-Timej,end

(6)

式中：Timen,m表示次用户n开始向信道m接入的时间；Timej,end表示次用户j不再使用信道m的时间。

由此可得蚂蚁转移概率为：

(7)

式中：N为蚂蚁接下来需经过的所有节点数，但禁忌表中的元素不包含在N中；α和β表示权重因子，分别表示信息素和信道效益的相对重要程度；tn,m,ξ表示信息素矩阵TN×M×ξ中的元素，表示蚂蚁在第ξ次迭代时，认知用户n在信道m处释放的信息素多少。

步骤4选择后继节点。蚂蚁的每一步移动表示一个可行路径，蚂蚁选择下一步的移动节点由行动判决依据n′决定：

(8)

式中:g表示0～1间的随机数；G取0.9;RW表示轮盘赌法。如果g

3 方案设计

在传统蚁群算法中，信息素矩阵各元素中信息素更新方式为：

(9)

(10)

式中：τi表示蚂蚁到达第i节点所经历时间(本文中，蚂蚁每到一个节点就会重置时间，同时记录蚂蚁从上一个节点出发到到达当前节点所需的时间)；τ表示循环过程所经历的总时间。

(11)

则可得最终的信息素更新时间系数ηi为：

(12)

则信息素矩阵TN×M×ξ中各元素的信息素更新如下：

(13)

当一只蚂蚁停留在某个节点不再继续移动时，算法的循环结束。蚂蚁在移动过程中，记录到达每一个节点的时间τ，然后根据蚂蚁移动的路径和到达各节点的时间对信息素矩阵中的各元素进行更新：

(14)

传统的蚁群算法是将信息素按蚂蚁所经历的节点数平均将信息素分配给每一个节点，而通过式(14)可以将信息素按照蚂蚁通过信道m到达每一个节点的时间来分配信息素，蚂蚁达到节点的时间越少，则分配的信息素越多；反之，蚂蚁达到节点的时间越多，则分配的信息素越少。

首先更新局部信息素，然后进一步更新全局信息素，在每次迭代完成后，重新计算每条路径上的信息素：

(15)

(16)

完成全局信息素更新后，首先将所有节点的信息素进行比较，然后按照信息素的大小顺序来分配信道。其中，信道的最终判决依据ωn为：

(17)

式中：εmax表示最大迭代次数。经εmax次迭代后，将信道分配给信息素最大的认知用户。分配完成之后需将信息素矩阵初始化，然后进行下一轮分配。

4 实验仿真及分析

假设仿真实验区域为一个30×30的网格，该网格区域中认知用户总个数为20个，可提供给认知用户使用的信道总数量为30个，每个认知用户的干扰范围d设为[3,6]。各个认知用户先不进行任何行动，当主用户未对其授权频段进行使用时，认知用户则根据分配的频谱乘机接入到该频谱。根据上述参数则可计算出可用频谱矩阵L、干扰约束矩阵C和信道效益矩阵B。假定搜索蚂蚁数量X=25，最大迭代次数εmax=100，信息素强度Q=2，信息素挥发因子ρ=0.11，信息素指数为1，启发式信息指数为3，初始信息量c=5，MAXPC=20。仿真共进行50次独立实验并记录结果，且每次实验时的矩阵L、B和C均随机生成。将本文IPAC算法与传统AOC算法[7]、QGA算法[14]、CSGC算法[15]在网络收益和、系统公平性、收敛速度和系统吞吐量四个方面的性能进行比较。

图1为不同可用频谱数量下，本文算法与AOC算法、QGA算法的网络收益和比较。可以看出，随着可用频谱数量m的不断增加，本文算法的网络收益总和始终高于AOC算法和QGA算法。这是由于引入的时间参数对信道的效益起到了较好的调节作用，大大减少了认知用户的搜索时间，从而使系统的网络收益得到显著提高。

图1 三种算法在可用频谱数不同时的网络收益和

图2为不同认知用户数量下，本文算法与AOC算法、QGA算法的网络收益和比较。可以看出，当认知用户数量不断增加时，三种算法的网络收益和都在减小。这是由于随着认知用户数量不断增多，作用于可用频谱上的干扰也随之增多，从而导致分配可用频谱的时间也相应变长。但由于本文算法与AOC算法、QGA算法相比收敛速度较高，所以当频谱数量不变时，认知用户可以做出有利选择，获得更好的网络收益。

图2 三种算法在认知用户数不同时的网络收益和

图3为不同认知用户数量下，本文算法与AOC算法、QGA算法的系统公平性比较。可以看出，本文算法的系统公平性始终优于AOC算法和QGA算法。这是由于随着认知用户数量不断增加，认知用户之间的竞争也随之增大，本文算法通过比较认知用户的信道使用情况来权衡频谱分配公平性，使系统公平性得到显著提高。

图3 三种算法在认知用户数不同时的公平性

图4为不同认知用户数量下，本文算法与AOC算法、CSGC算法的收敛速度比较。可以看出，本文算法的收敛速度要始终快于AOC算法和CSGC算法。这是由于本文算法引入了时间效率这一量化因子，使系统减少了认知用户的搜索时间，大幅节约了时间开销。

图4 三种算法在认知用户数不同时的收敛速度

图5为不同可用频谱数量下，本文算法与AOC算法、CSGC算法的收敛速度比较。可以看出，当可用频谱数量增加时，三种算法的系统的吞吐量都在增加。但是由于本文算法的收敛速度明显比AOC算法和CSGC算法快，所以系统的吞吐量显著高于两种算法，可以有效改善系统的整体性能。

图5 三种算法在可用频谱数不同时的系统吞吐量

综上所述，本文算法由于引入了时间效率这一量化因子，大大减少了认知用户的搜索时间，使认知用户能更快速地接入到可用频谱，具有更快的收敛速度，进而获得了更好的网络收益和以及系统吞吐量。同时，其通过比较认知用户的信道使用情况来权衡频谱分配公平性，显著提高了系统频谱分配的公平性。因此，本文算法在网络收益和、系统公平性、收敛速度和系统吞吐量四个方面的性能均优于AOC算法、QGA算法和CSGC算法。

5 结 语

本文通过引入时间因子对信息素的计算方法进行改进，给出一种基于多态蚁群优化算法的认知无线电频谱分配方案。通过动态考虑认知用户的频谱接入时间，有效加快频谱分配速度，降低认知用户间的竞争，大幅提高信道利用率，同时也有效提升了系统的公平性。仿真实验结果表明，与传统认知无线电频谱分配算法相比，本文算法可以显著提升系统的网络收益、公平性、收敛速度和吞吐量等性能。