1频谱分配模型
［4］频谱分配是指根据需要接入系统的节点数目及其服务要求将频谱分配给一个或多个指定节点。图1表示的就是对频谱分配问题的一个简单描述［3］。在效益最大化的频谱分配模型中，由认知用户构成的网络拓扑结构可抽象成图G(V，E，L)。V是顶点集合，一个顶点代表一个认知用户;E是边的集合，若两个认知用户i，j的干扰范围不出现重叠，则ei，j=0，否则ei，j=1;L用来表示次用户的信道可用性。如图2所示。图中1－5代表认知用户，有三个信道A、B、C对于认知用户来说是机会式可用的。I－IV表示主用户，它们目前正占用信道A、B、C。假设所有信道拥有相同的带宽，主用户和次用户都具有相同的功率，所有的主用户在各个信道上覆盖的区域大小相同，即具有相同的覆盖半径，同理认知用户在个信道上具有相同的干扰半径。频谱共享协议规定，主用户占用的信道不能被其邻近的认知用户使用。因此，在主用户I－IV干扰范围内的认知用户不能与主用户使用同一频段。在图中，虚线组成的圆代表各主用户的干扰范围。图论着色模型中的频谱分配问题可用信道矩阵、效益矩阵、干扰约束矩阵和分配矩阵描述。它们的定义如下:1)信道的可用矩阵L：其中ln，m=1表示认知用户n可以使用信道m;ln，m=0表示认知用户n不能使用信道m。2)干扰矩阵C:C={cn，k，mcn，k，m∈{0，1}}N×N×M(2)它是一个三维矩阵，当认知用户n和k同时使用信道m，将会造成干扰，此时cn，k，m=1;若同时使用m时不产生干扰，则cn，k，m=0。干扰矩阵C与可用矩阵L也有着关联，即cn，k，m≤ln，m×lk，m;当n=k时，cn，n，m=1－ln，m，此时，干扰矩阵仅由信道的可用矩阵决定。3)效益矩阵B:B={bnmbnm＞0}N×M(3)B表示认知用户n使用信道m时所获得的效益权重。bn，m=α表示认知用户n使用信道m时获得效用权重为α;bn，m=0表示认知用户n不能够使用信道m。4)无干扰的频谱分配矩阵A:A=an，man，m∈{0，1}，an，m≤ln，{}mN×M(4)其中，an，m=1表示信道m被分配给了用户n;否则an，m=0。矩阵A必须满足无干扰限制条件:an，m+ak，m≤1，ifcn，k，m=1，0＜n，k＜N，0＜m＜M。在频谱分配过程中，单个认知用户n获得的效益定义为:rn=∑Mm=1an，m·bn，m。所有认知用户获得的效益可组成矩阵Ｒ=rn=∑Mm=1an，m·bn，{}mN×1。把所有无干扰的频谱分配集定义为Λ(L，C)N×M。频谱分配的系统效益定义如下:U(Ｒ)=∑Nn=1rn=∑Nn=1∑Mm=1an，m．bn，m(5)同时为了更好的验证算法的新能，本文还引入了评价频谱分配的时间开销的方法。假设每次分配的循环时间均为t，这样算法总的分配时间开销等于算法循环次数乘以t。算法的循环次数为矩阵A的矩阵范数am1。T为算法分配的总的时间开销。
2基于黄金分割率的混合自适应遗传算法
自适应交叉变异策略是由SrinivasM、PatnaikLM等提出来的［10］，在自适应遗传算法中，交叉概率和变异概率不是一个固定的值，而是按群体的适应度进行自适应调整。因为个体适应度值越接近最大适应度值，交叉概率与变异概率就越小;当等于最大适应度值时，交叉概率和变异概率为零。这种调整方法在群体处于进化后期时是比较合适的，但在进化初期是不利的，因为在进化初期群体中的较优个体几乎处于一种不发生变化的状态，而此时的优良个体不一定是优化的全局最优解，这增加了进化走向局部最优解的可能性。因此，本文引入了混合的自适应思想［11］。混合的自适应遗传算法改进了上述的基本自适应遗传算法的不足，它是根据进化代数来判断是否进行自适应交叉和变异的，在进化初期采用固定的交叉和变异概率，在种群的进化后期采用自适应交叉和变异概率。但考虑到当前代群体中的较优个体应具有较高的交叉和变异概率，因此，在最优个体不被破坏仍然保留的情况下，要确定以最佳的自适应点进行交叉和变异。本文又引入了黄金分割率［12］来进行最佳自适应点的选择。GA是一种模拟生物进化过程的算法，因此极有可能隐藏着黄金分割率。在改进的自适应算法公式中引入黄金分割率，依照“去坏留好”的原则、对称原则、等比收缩原则来逐步缩小搜索范围。每次搜索空间缩小0.382倍或0.618倍，直至缩为一点。这是一个收敛速度很快的一维搜索方法。改进的交叉和变异概率公式如下:自适应交叉概率Pc如(10)式所示:其中:f为要变异个体的适应度值，f'为要交叉的两个个体中较大的适应度值，favg为平均适应度值，fmax为最大适应度值，Pcmax=0.9，Pmmax=0.1。
3基于黄金分割率的混合自适应遗传算法的频谱分配模型
本文算法中的可用频谱矩阵L、效益矩阵B、干扰矩阵C都是按照上述频谱分配模型定义的。把目标函数(系统效益、时间开销)的表达式作为遗传算法的适应度函数。编码方式采用实数编码。实数编码就是将问题的解用一个实数来表示。实数编码直接在解的表现型上进行遗传操作，也就是说，在执行中，遗传空间就是问题解空间，染色体将直接反映优化问题的规律和特性。本文的遗传算法中的核心算子:选择、交叉、变异操作分别如下方法进行［11］:1)选择算子轮盘赌选择方法是一种基于适应度值的回放式随机采样的方法。它的基本思想是:每个个体被选中的概率都与它的适应度值大小成正比。设种群规模为n，种群中的一个个体i的适应度值为fi为，则该个体被选择的概率pi如式(12)所示:2)交叉算子双点交叉的具体操作是:在个体串中随机的设定两个交叉点，然后将两个交叉点之间的个体结构进行互换。3)变异算子变异操作决定了遗传算法的局部搜索能力，能够维持群体的多样性和防止出现早熟现象。本文采用基本位变异算子，即个体中的基因实现0和1之间的翻转。在本文的频谱分配方案中，每一条染色体的二进制串表示一种可能的频谱分配，由于无干扰频谱分配A与可用矩阵L中等于0的元素位置相对应，而且每条染色体的长度由可用矩阵L中等于1的元素个数来决定。因此矩阵A的更新只需将每代新的染色体的每个基因依次取代矩阵L中为1的元素即可。此外，每次更新结束后，还需作适当的处理使新的矩阵A满足C的条件，最终获得的无干扰分配矩阵A就是一种可行的频谱分配方案。具体方法为:对C中所有满足cn，k，m=1且的n≠kn和k，判断An，m和Ak，m是否均为1，若是，将其中之一置为0。综上所述，将基于黄金分割率的混合自适应遗传算法应用到认知无线电频谱分配，一般步骤为:1)初始化可用频谱矩阵、效益矩阵和干扰矩阵，该优化问题的维数为l=∑Nn=1∑Mm=1ln，m，种群大小为P。记录可用矩阵L中为1的元素，即L1={(n，m)|ln，m=1}，矩阵中的元素按n、m递增的方式进行排列。维数l的值等于L1中元素的个数;2)在进化的第0代，即g=0时，根据二进制编码初始化种群;3)优化种群Q(g)得到二进制串P(g);4)P(g)中每个染色体的第j位映射到an，m中，1≤j≤l，(n，m)是L1中第j个元素。对于全部的频谱m，找出所有满足cn，k，m=1且n≠k的认知用户集合，验证分配矩阵A中的第n行m列及k行m列的元素是否全部为1，若是，随机将其中的一个元素置0，另一个保持不变;5)频谱分配中的效益函数作为适应度函数，计算出适应度函数，之后将结果保存到B(g)中;6)用轮盘赌选择法，进行双点变异交叉操作，并进行种群Q(g)的更新;其中交叉变异操作的过程为:首先计算进化代数，判断是否满足进行自适应交叉变异的条件，若满足，则运用(10)(11)式计算交叉变异概率并进行自适应交叉变异操作，否则进行固定参数的交叉及变异操作;7)断是否有达到进化的终止代数，若是将B(g)中保存的最优解映射成矩阵A的形式即已经到达了最佳分配则算法结束;否则继续循环执行;8)g+1;9)测量种群Q(g－1)，产生确定状态P(g)，转至步骤4)。
4仿真结果与分析
认知无线电频谱分配性能最常见的评价方式是系统效益和公平性，因此，为了验证改进遗传算法的性能，把本文算法与自适应遗传算法在系统效益和算法的时间开销上进行了比较，设定认知用户数为10，主用户数为20，频带数为20，运用Matlab进行了仿真。为了简化问题，在仿真试验中，假设系统是个准静态无噪声的无线系统，且不考虑功率控制因素;也是就是系统在一次完整的频谱分配过程中，每个认知用户的可用信道和干扰关系保持不变。同时，所有主用户在各个信道上的干扰半径相同，所有认知用户的干扰半径也相同。算法仿真中的L、B、C矩阵如表1所示。图3表示的是基本遗传算法，自适应遗传算法和基于黄金分割率的自适应遗传算法系统的平均效益随着迭代次数的变化曲线图。有上图可以看出，随着迭代次数的增加，系统效益逐渐增加，基本遗传算法和自适应遗传算法在迭代500次左右的时候达到全局最优解，而本文算法在迭代300次就达到了最优解，很明显比其它算法的收收敛速度更快，而且获得的系统效益也更好一点。图4表示的是传统的遗传算法和自适应遗传算法，基于黄金分割率的混合自适应遗传算法的系统效益随着认知用户改变的变化曲线图。随着认知用户的增加，系统效益逐渐减少。但是，本文算法的系统效益最好，其次是自适应算法，图5表示的是网络效益随试验次数的变化曲线。由图5可以看出，本文算法得到的网络效益只有很少部分上效果不明显，大部分都是明显优于其它两种算法。图6表示的是本文算法和自适应遗传算法的时间开销随迭代次数的变化曲线图，由图可以看出算法的时间开销随着迭代次数的增加逐渐上升，自适应算法和遗传算法的分配时间消耗相差不大，本文提出的算法的分配时间开销明显比基本遗传算法的要小。因此，此算法提高了频谱分配的效率。
5结束语
本文提出了融合黄金分割率的混合自适应遗传算法的频谱分配方案。第一，在计算交叉和变异概率时引入黄金分割率的思想，解决陷入局部最优解的问题;第二，运用混合自适应的思想，动态的调整使用固定的交叉变异还是自适应的交叉变异，有效解决了运算时间长的问题。仿真证明了该算法比传统自适应遗传算法具有更好的性能:提高了算法的搜索效率，收敛速度更快，系统的效益更大且不易陷入局部最优解。
作者：杨铁军 林培培 单位：河南工业大学信息科学与工程学院
