认知无线传感器网络频谱分配的一种改进方法

无线传感网络(Wireless Sensor Netowrks, WSNs)的通信以频谱资源为基础[1-3]。认知无线电和WSNs结合，产生了认知无线传感网络(Cognitive Radio Sensor Networks, CRSNs)[4,5]。认知无线传感网络节点依赖电池提供电能，但电池电量有限且难以更换。因此，认知无线传感网络使用的算法和相关技术都以节约能量为重点。然而，在车联网等实际应用中，认知无线传感网络对频谱及能量的需求很大[6-8]。节点不但需要检测频谱空穴，还要对数据进行监测，需要消耗大量能量[9-11]。在认知无线传感网络中，可通过降低节点能量损耗的方法提升频谱资源的利用率[12]。

动态频谱分配(Dynamic Spectrum Allocation, DSA)是与认知无线电原理类似的频谱切换技术[13]。动态频谱分配能敏锐地监测到哪一个频段当前是没有被使用的，记录并且共享所有频段的状态，对次用户的频段使用进行实时调整，及时并且合理地将频段分配给用户。动态频谱分配是对频谱资源的多次利用，在一定限度内能缓解频谱资源缺乏的情况，也不会降低信息的传输速率。根据认知无线传感网络中数据的传输能力、用户数量、信道繁忙程度等情况，动态频谱分配能按照客户需求和系统参数自动调整分配策略，避免频谱资源浪费。在共享有限的频谱资源方面，动态频谱分配技术具有较大的优势。

针对在认知无线传感网络中面临的频谱资源紧缺问题，文献[14]提出了一种蚁群算法(Ant colony Optimization, ACO)来提升网络效益，但该算法有早熟收敛的缺点。文献[15]提出了模拟退火(Simulated Annealing，SA)算法，该算法可以大大缩短频谱分配所需的时间，但有进化停滞的缺陷。文献[16]提出了一种概率频谱接入的频谱分配方法，该方法分配效率较高，但分配结果存在频谱冲突的可能性。文献[17]提出了一种智能联合频谱分配方法，采用了交替方向优化技术，获得较好的优化结果，但算法复杂度较高。文献[18]提出了一种吞吐量最大化的联合频谱分配方法，能够最大化系统吞吐量，但算法未综合考虑网络效益。

针对以上问题，笔者提出了一种新的混沌动态克隆进化算法(Chaotic Adaptive Clone Evolutionary Algorithm, CACEA)，并与蚁群算法、模拟退火算法进行仿真对比。仿真结果显示，利用新的混沌动态克隆进化算法能够解决认知无线电中的动态频谱分配问题，且分配效益值较蚁群算法和模拟退火算法有明显提升。

1 频谱分配问题的系统模型

图论着色模型可由效益矩阵E、可用矩阵M、干扰矩阵H与分配矩阵D表示。认知无线传感网络中I个频谱可当作无向图中的I个顶点着色问题。当网络范围内主用户数和次用户数都是J时，模型可由以下矩阵表示：

(1)分配矩阵：由D={dj, i|dj, i∈{0, 1}}J×I表示。若dj, i为1，则表示用户j使用频谱i；否则用户j未使用频谱i。初始分配矩阵表明该网络在初始条件下频谱的分配状况，一般第一次分配设置成零矩阵。

(2)可用矩阵：由M={mj, i|mj, i∈(0, 1)}}J×I表示。当频谱mj, i为1时，频谱i能够被分配给次用户j；否则，当mj, i为0时，频谱i不可被分配给次用户j。

(3)干扰矩阵：由H={hj, k, i|hj, k, i∈{0, 1}}J×J×I表示。当hj, k, i为0时，表示用户j和k相互之间是没有干扰的，而且能够共用频谱i；否则，会互相干扰，不能同时使用。若j=k，则hj,j, i=1-mj, i。

(4)效益矩阵：由E={ej, i}J×I表示。 ej, i的值为次用户j在使用频谱i时的收益值，例如：频谱利用率。

模型中的j和k是认知无线传感网络中的两个传感器的节点，i是信道。因为分配矩阵D的前提条件是无干扰条件的影响，因此可用矩阵M和干扰矩阵H中与之对应的元素，值是mj, i=1，hj, k, i=0。

在式(1) 和式(2)中，当频谱分配没有冲突时，则频谱分配给用户j所产生的网络效益值是rj， R为目标函数，通过计算目标函数，可找到每一次迭代中网络效益值最好的个体。

分配矩阵D要满足在式(3)中根据干扰矩阵的约束条件，那么两用户之间没有干扰产生。

(1)

(2)

dj, idk, i=0, if hj, k, i=1 。

(3)

给出了吞吐量的权值矩阵T={tj, i}J×I用来评价混沌动态克隆进化算法在吞吐量方面的性能，tj, i表示频谱i被分配给用户j时的吞吐量的值。吞吐量F的计算公式如下，

(4)

2 基于改进方法的动态频谱分配

进化算法(Evolutionary Algorithm, EA)根据自然界中优胜劣汰适者生存原理得出。该算法结合了孟德尔的自由组合、分离定律及达尔文的进化论。进化算法过程有：根据问题进行染色体编码操作，产生原始的种群，计算种群的适应度，选择，交叉，变异以及判断是否符合算法停止的条件。传统进化算法具有适应度函数的挑选方式太多，“早熟”现象以及接近局部最优不能达到全局最优的缺点。许多研究人员对进化算法的改善主要在遗传算子的选择、编码形式的选取、适应度函数的挑选等方面。经过改善的进化算法是一个搜索式的启发性算法，在处理最优化问题方面具有较好的效果，可用来分配频谱，提高算法的性能。根据进化算法原理，设计并提出了一种混沌动态克隆进化算法，设计了染色体的编码方式，从而合理地表示基因形式。

2.1 种群编码

混沌动态克隆进化算法根据实际问题进行编码。在原始状态下，用户的位置具有随机性，按照其位置初始化分配矩阵D、可用矩阵M、干扰矩阵H和效益矩阵E。染色体是算法的基本单位，若每一个染色体是可行的，没有冲突的解，分配矩阵D={dj, i|dj, i∈{0, 1}}J×I的初始值中的每个元素值与染色体一一对应。分配矩阵D和可用矩阵M之间存在映射关系。若矩阵M中元素是0，则表示不能给用户分配信道；当矩阵M中元素为1时，在其对应位置上，混沌动态克隆进化算法中的染色体的基因值即分配矩阵D中的元素值。

2.2 产生初始种群

在混沌动态克隆进化算法中，可以用随机的方法得到初始种群，在频谱分配问题中需要选取适当的种群数量以保证算法既能找到最优解又使执行时间不会过长。混沌算子是一种能够提高全局搜素能力的算子。在混沌动态克隆进化算法中加入了该算子。首先通过混沌映射产生初始种群，将混沌序列加入选择、交叉、变异操作中，初始种群被划分为多个子种群。一维Logistic映射的特点是非周期且不收敛，混沌算子可提高全局的搜索能力，避免早熟未收敛的问题。一维Logistic映射如下所示：

an+1=μan(1-an) ,

(5)

(6)

其中，an是第n次映射产生的混沌序列值；an+1是第n+1次映射产生的混沌序列值，生成的混沌序列值均为0到1之间的随机小数；μ为常量参数。为了保证映射得到的an+1始终位于[0, 1]内，取μ∈[0, 4]。当μ为不同值时，式(5)会表现出不同的动力学极限行为。当μ∈(3.569 9, 4]时，系统达到混沌状态，当μ=4时，系统达到完全混沌状态。在式(6)中，分配矩阵中的元素可以由混沌序列产生。

2.3 选择、交叉和变异

在混沌动态克隆进化算法中，选择操作将种群中的个体按照网络效益值的大小排序，使用轮盘赌算法选择网络效益值较好的个体。混沌动态克隆进化算法中最重要的部分是交叉和变异操作。在混沌动态克隆进化算法中，变异概率的大小决定了搜索过程的快慢。若变异概率过小，则生成新的个体的可能性会过小且会导致算法的收敛速度过慢，从而出现早熟现象。交叉概率影响个体生成，可以通过加入自适应算子用于调整交叉概率和变异概率。依据式(2)中网络效益值的大小及时调节，减少冗余计算，提高算法的性能。

在混沌动态克隆进化算法中，交叉概率和变异概率可通过下式计算：

(7)

(8)

其中，Pc表示交叉概率；Pm表示变异概率；Rmax代表所有个体中最优的网络效益值；R′表示在两个个体中较大的网络效益值；Ravg代表在每一次迭代中，所有个体的网络效益平均值；R为将要变异的个体的网络效益值。x1、x2、x3、x4为在0至1之间的数，通过加入自适应算子的方法调节Pc和Pm。克隆算子可使算法不易陷入局部最优解，所以加入了克隆算子。在混沌动态克隆进化算法中，首先随机生成初始抗体种群，计算抗原和抗体的亲和度，再根据亲和度判断个体是否可被克隆，从而产生子抗体。

2.4 适应度函数和终止条件

在混沌动态克隆进化算法中，适应度函数是评价个体优劣的方式，在式(2)中，把求解最大网络效益值作为目标函数，在每一代选择、交叉、变异的操作后进行计算适应度并评价适应度，从而提高频谱利用率。通过设置遗传代数决定算法是否终止。如果已到达，则输出网络效益值和吞吐量；如果未到达，则继续执行。

2.5 算法流程

算法流程如下：

(1) 构造满足条件的个体。首先通过一维Logistic映射的方法对初始种群编码。

(2) 种群初始化。选择适当的种群数量并随机生成初始种群。

(3) 选择。使用轮盘赌的选择方法选取网络效益值较大的个体。

(4) 交叉、变异。利用自适应算子调节交叉概率与变异概率，进而生成一个全新种群。

(5) 计算适应度，判断结果是否满足终止条件，满足则输出结果，否则执行第(3)、(4)、(5)步。

3 仿真分析

仿真实验基于9600型号的奔腾i5处理器，操作系统采用Windows 7，4GB内存，仿真软件使用MATLAB 7。在仿真中，3种算法的个体数均设为40，迭代均为100次。所提混沌动态克隆进化算法的交叉概率设置为0.85，变异概率设置为0.05。为评价混沌动态克隆进化算法的性能，将算法与ACO、SA进行了仿真比较。由式(2)计算网络效益值。在图1和图2中，设定频带的数量设为5，用户的数量分别为20、30，经过100次迭代，记录了在不同情况下3种算法的网络效益值并得到了3种算法网络效益值的变化曲线。

图1 网络效益值比较图(认知用户数为20)

图2 网络效益值比较图(认知用户数为30)

在图1中，设置频带个数为5、认知用户数为20。由仿真结果可知，CACEA的网络效益值大于ACO 算法和SA算法的。经过100次迭代后，CACEA的网络效益值为124.59，ACO的网络效益值为99.94，SA的网络效益值为84.96，即CACEA的网络效益值较高，算法性能最好。在图2中，频带数量不变，用户数增大到30。由仿真结果同样可知，CACEA 相比ACO和SA，网络效益值较高。

为了比较3种算法的复杂度和系统开销，针对图1和图2的两种仿真参数，表1对比了3种算法运行所需的时间。从表1中可以看出，CACEA算法所需运行时间略少，即在网络效益值获得提升时，其在算法复杂度和系统开销方面，相比ACO和SA略有下降。当频带的数量设为5，用户数量为20时，CACEA的时间复杂度相比ACO的下降了约7.06%，相比SA的下降了约11.77%；当用户数量为30时，CACEA的时间复杂度相比ACO的下降了约4.45%，相比SA的下降了约7.54%。

表1 3种算法所需时间对比表 s

图3 吞吐量比较图(频谱数为5)

图4 吞吐量比较图(频谱数为10)

在图3和图4中给出了CACEA算法、ACO算法与SA算法在频谱数分别为5和10的情况下的吞吐量的变化情况。由图可知，当认知用户数由5增大到50时，吞吐量也不断增加。仿真显示，用户数相同时，CACEA算法比ACO和SA有更大的吞吐量，进一步说明CACEA能够提高CRSNs的吞吐量和网络效益。

4 结束语

为了能够将频谱更高效地分配给用户，提高认知无线传感器网络的频谱效率，解决认知无线传感器网络频谱分配问题，提出了一种混沌动态克隆进化算法，设计了系统模型。为了加快算法的收敛速度，设计了对应的适应度函数及混沌发生器，并提出了新的克隆算子和新的自适应算子。借助软件进行了仿真实验，将CACEA和ACO、SA算法进行了仿真比较。由仿真结果可知，混沌动态克隆进化算法在解决频谱分配的问题时，比ACO、SA更有优势，具有全局搜索特性，能够加快算法收敛速度并实现网络效益最大化。

认知无线传感网络频谱分配涉及多方面的理论、方法和技术，在实际系统实现方面还有许多新问题需要解决。笔者未来将在系统参数动态调整、复杂环境下异构节点频谱分配方面进行更为深入的研究。