基于遗传算法的蜂窝网络接入信道动态分配方案的设计

1、基于遗传算法的蜂窝网络接入信道动态分配方案的设计摘 要： 蜂窝网络中，使用信道复用技术能够在很大程度上提高移动通信的容量和质量。但是，信道复用过程中会产生不同程度的电子干扰问题，使得信道复用的作用大打折扣。传统的进行信道优化的方法很多，但是效果都不是很理想。这里利用遗传算法进行蜂窝网络接入信道的动态分配，主要通过对集中常出现的信道干扰问题加上一些约束条件，这样建立的数学模型能够获得一最小干扰信号的信道分配方案，在很大程度上避免了移动用户之间的干扰问题。关键词： 遗传算法； 信道重用； 信号干扰； 动态分配中图分类号： TN911.22?34 文献标识码： A 文章编号： 1004?373X（2

2、016）15?0005?03Abstract： The channel reuse technology is used in cellular network to improve the capacity of mobile communication and communication quality to a great extent. However， the electronic jamming problems with varying degrees can be generated in the process of channel reuse， which makes th

3、e effect of channel reuse weaken. The traditional channel optimization methods are massive， but the effect of them is undesirable. The dynamic allocation of cellular network access channel based on genetic algorithm is studied. For the interference problems appearing in the channel frequently， the m

4、athematical model was established by adding some constraint conditions to obtain a channel allocation scheme with minimum interference signal， and avoid the common interference problems of mobile users to a great extent.Keywords： genetic algorithm； channel reuse； signal interference； dynamic allocat

5、ion0 引 言现在的移动通信主要采用蜂窝移动通信技术，移动通信用户的增长率非常快，为了提高移动通信的质量和效率，需要充分利用信道复用技术，这样就能在很大程度上提高移动通信的容量和资源的使用频率。但是，信道复用技术本身是有缺陷的：信道复用会产生电子干扰从而使得移动通信的质量大打折扣。所以，需要采用各种优化算法进行信道分配。蜂窝网络信道分配问题就是一个优化问题，也是一个优化方面的难题。可以进行信道分配优化的算法很多：神经网络算法、粒子优化算法、模拟退火算法等。但是这些算法在解决信道分配方面的优化结构上都不是很理想。本文研究的是基于遗传算法的蜂窝网络接入信道动态分配方案，主要目的是解决移动蜂窝网络

6、中的几种主要干扰问题。1 遗传算法概述遗传算法是一种智能型的搜索算法，能够利用遗传算法计算解空间满足约束条件的最优解，遗传算法求解空间最优解的步骤主要包括编码、初始化、适应值函数确定、选择、交叉和变异等几个基本的步骤。（1） 编码：在解空间中搜索最优解的过程中，首先要将数据编码成一个字符串，这个字符串就是遗传算法中的一个基因型数据，这些数据在字符串中会进行不同的组合，这样就形成了不同的基因型字符串。（2） 生成初始种群：初始种群的生成是随机的，选择个随机的初始字符串，每个字符串可以作为一个染色体，个染色体就是一个最初的群体，也是遗传算法开始迭代的种群。（3） 适应值函数的确定：适应性函数的作用

7、是能够表示最终的解空间的解是优是劣。所以，针对问题的不同适应值函数也是不一样的。（4） 选择：要进行最优解的寻找，就要从当前种群中找到最为优良的染色体做为父代进行繁殖，找到这个优良父代的过程就是选择。进行选择的依据是达尔文的适者生存原则，只有能够达到最佳适用性的父代才能被选择继续下去，这样的父代会为下一代贡献更多的后代。（5） 交叉：交叉操作是将两个染色体中的数据进行交换，从而可以产生新的染色体，也就是交叉可以产生新一代的个体，这些新个体能够将其父辈的特性进行组合。（6） 变异：在某一代的群体中随机选择一个个体，然后对这个个体中的数据按照某种规律进行随机的变化，这就是遗传算法的变异。遗传算法就

8、是模拟生物的进化，所以遗传算法的变异概率是很低的，一般在0.0010.01之间。通过遗传算法的变异操作有可能产生新的个体。遗传算法在解空间中搜索最优解的流程如图1所示。2 蜂窝网络拓扑结构蜂窝网络之所以被广泛应用于移动通信中，是因为数学领域的一个定理。如果一个平面以多个同半径的圆形覆盖，当圆心和正六边形网格的各正六边形中心重合，也就是圆心在正三角网格的格点上时，圆的数量是最少的。虽然，在实际的移动通信中可以采用圆形结构实现网络的构建，但是这样做的成本是比较高的。所以，从节约成本的角度考虑，移动通信的网络建设采用了正三角网格，也就是简单六角网格这也是蜂窝网络的由来。之所以在个人移动通信服务系统中

9、使用蜂窝网络的拓扑结构是因为蜂窝网络能够提高移动通信的效率和网络的有效利用率。蜂窝网络的拓扑结构如图2所示。从图2可以看出，蜂窝网络中的每个蜂窝都表示一个小区，小区的大小不是固定的，需要根据其实际的大小和整个蜂窝网络的总用户数来确定。如果是在用户密集的区域设置蜂窝网络，需要采用的小区必须是小尺寸的。还有的情况下，用户会有较高的平均运动速度，这种情况下，采用的小区尺寸适合大尺寸的。另外，如果是用户密度较低的区域，也适合大尺寸的小区。3 信道动态分配方案设计3.1 信道动态分配数学建模在进行数学建模时，要充分考虑所有的约束问题，本研究的约束主要有三种：同频约束、邻频约束和同位置约束。所以，首先要建

10、立一个兼容矩阵：如果小区为个，那么就可以设置为的对称矩阵。该矩阵用来表示小区之间的频率兼容性的大小。表示第个小区和第个小区之间的信道间隔，也就是同频约束和邻频约束。而在对角线上的所有元素表示在同一个小区内分配的任意两个信道之间的最小间隔的大小，也就是同位置约束。每个小区的话务需求量不同，所以需要先建立一个小区话务需求向量个小区的信道需求关系就可以描述为一个的向量，就是第个小区内的信道数量，如果小区需求的话务量发生了变化，也随着发生变化。假设蜂窝网络中的可用信道数量为个，就可以采用的二维矩阵表示信道的分配方案，用矩阵的列表示信道数目，行表示小区的数目，如果信道是分配给小区的，就将设置为1，否则为

11、0。小区和信道的关系不可以违反三种兼容约束，所以需要建立一个违反矩阵如果小区与之间违反兼容约束，则就设置为1，否则设置为0。还需要对小区之间违反兼容约束的信道数目进行描述，所以再建立一个矩阵就是小区与小区之间违反兼容约束的信道数目，如果信道是分配给小区的一个信道，是分配给小区的一个信道，如果就是小区内实际分配信道的最小间隔距离。就是要满足同位置约束时同小区内分配的信道的最小间隔距离。式（1）就是要实现的目标函数，使得小区间违反兼容约束的小区和信道的数量都要达到最小；式（2）表示同一小区内的信道数要满足话务需求；式（3）表示同一小区内的最大用户数不能大于设置的小区容量，也就是；式（4）表示同一小

12、区内设计分配的信道的最小间隔必须大于或者等于同位置约束。其中， 。3.2 信道动态分配策略（1） 定义适用值函数设定一个最小目标函数可以将适应值函数设定为：这就是信道分配方案的适应值。如果能得到越小的函数值，得到的适应值就越大，所以本研究的目标就是能够找到一组能够使得适应值最大的信道分配方案。（2） 编码及解码信道分配方案中，需要在同一小区中设置一个信道中的最小频率间隔，所以本研究中选取的编码方案为：假设有个话务请求 ，用长度为的二进制串表示个体，表示连续元素间的最小间隔，的第一位用1表示，它后面的个0用【1】表示。然而，当1的位置不是在的第一个位置，而是在后面的个位置时，编码就会出现问题，所

13、以本研究在初始的二进制串编码中，就在个二进制串的后面补了个0，这样，二进制串的长度就发生了变化，变为小区信道分配采用的是最小间隔编码法，【1】被解码为1和个0，每个个体的长度为需要将个0减去，这样就得到了一个动态信道分配矩阵也就知道信道是如何在每个小区内实际分配的。（3） 选择策略本研究采用的选择策略是轮盘赌选择法，该方法的选择依据同样是个体适应值的大小，如果个体适应值小它就很有可能被丢弃，如果个体的适应值大，它被选中的概率就大。为了保证最佳个体在选择和交叉的过程中不被丢失，本研究还在算法的实施过程中设置了最佳个体保存策略，通过该策略就能保存每一代的最佳个体，把最佳个体复制到下一代，用其替换最

14、差个体，这样就能保证群体中的最佳个体越来越多，最快的达到最终结果，提高了算法的收敛速度。（4） 交叉算子需要在最小间隔编码的种群中进行交叉操作，需要交叉的是两个染色体，通过交叉产生新的后代。本研究采用的是固定交叉算子，这样能够保证在交叉的过程中，始终满足信道分配需求。设定两个染色体分别为和创建一个栈，如果染色体的对应位置的两个基因值和异或为1，也就是和不能同时为1或者同时为0，就把当前的放进栈中。随机产生两个交叉点和将这两点交叉，从开始向进行遍历，如果在一个点使得和异或不为1，把放入其中，然后继续，直到找到另一点使得和异或为1。然后，比较和栈顶元素如果等于把推进栈中，否则，交换 和将从栈中弹出

15、。重复上述操作直到遍历到（5） 变异算子染色体的变异过程同样需要满足信道的分配需求，所以本研究采用的变异算法也是固定的。变异操作在最小间隔编码的种群中进行，先根据变异率选出需要变异的基因然后按照随机的方式选中一个位置取出对应的基因如果和异或为1，就将和交换。4 结 语本文提出了一种动态信道分配方案，该方案利用遗传算法在建立数学模型时，对常见的对信道复用有影响的几种电子干扰进行了约束，在进行动态信道分配时，利用建立的数学模型得到了一组干扰最小的信道动态分配方案。参考文献【1】 王联国，洪 毅，赵付青，等.一种改进的人工鱼群算法.计算机工程，2008，34（19）：192?193.【2】 于雪晶，

16、麻肖妃，夏斌，等.动态粒子群优化算法.计算机工程，2010，36（4）：193?197.【3】 党安红，张敏，朱世华，等.一种新的优化动态信道分配策略及建模分析.电子学报，2004，32（7）：1152?1155.【4】 张敏，党安红.一种基于改进神经网络的动态信道分配算法.计算机工程与应用，2005（28）：124?126.【5】 卢瑜.遗传算法在移动通信传输领域的应用.工会博览，2009（1）：56?57.【6】 何迪，贾振红.基于混洗蛙跳算法的频率分配方法.计算机工程，2011，37（21）：133?135.【7】 LIMA M A C， ARAUJO A F R， CESAR A C.

17、 Adaptive genetic algorithms for dynamic channel assignment in mobile cellular communication systems . IEEE transactions on vehicular technology， 2007， 56（5）： 2685?2696. 徐俊杰，忻展红.基于微正则退火的频率分配方法.北京邮电大学学报，2007，30（2）：67?70. 朱志宇，姜长生.基于混沌神经网络移动通信信道分配方法研究.电子与信息学报，2005，27（9）：1429?1432. 朱晓锦，陈艳春，邵勇，等.面向信道分配的分段退火混沌神经网络模型.通信学报，2008，29（5）：122?127. VIDYARTHI G， NGOM A， STOJMENOVIC I. A hybrid channel assignment approach using an efficient evolutionary strategy in wireless mobile networks . IEEE transactions on vehicular technology， 2005， 54（5）： 1887?