基于改进蜂群算法的移动通信信道分配方法

基于改进蜂群算法的移动通信信道分配方法

1基于改进的人工蜂群算法在移动通信系统中，移动用户的快速增加与有限频率资源之间存在矛盾。为了提高有限频率资源的利用率，采用频道分布技术是一种明显的方法。通常是根据干扰约束条件以及信道分配问题模型,按照不同的算法求解信道的最佳分配方案。在早期,信道分配问题的研究大多是以图形理论或启发式方法为基础的,近年来,主要用神经网络、遗传算法、模拟退火算法和微正则退火算法来处理信道分配问题。但在搜索最优解过程中,它们依然存在收敛时间较长,容易陷入或难以摆脱局部最优解等缺点。为了解决上述缺点,利用固定信道分配的数学模型,在普通人工蜂群算法的基础上,提出了一种用改进的人工蜂群算法来求解最佳信道分配的方案。人工蜂群算法是一类新兴的基于蜜蜂群智能搜索行为的优化算法,它与其他智能算法一样具有优良的优化性能。由于智能算法自身还存在一定缺陷,许多研究者提出了一些改进措施并应用于不同的领域。本文针对人工蜂群算法收敛速度慢,易陷入局部最优等缺点,将人工蜂群算法进行改进,并用于解决固定信道分配问题;仿真证明了该算法的优越性。2数值分配算法信道分配问题即频率分配问题,其基本模型是可行性频率分配,目标是在不违反干扰约束的前提下,所有小区都能分配到所需数量的频点。通常只考虑三种主要干扰约束条件:同频干扰(CCC)、邻频干扰(ACC)、共地干扰(CSC)。通常用一个N´N维的兼容矩阵来表示以上主要的干扰约束条件(N为蜂窝系统的小区数),矩阵C中对角元素Cij表示分配给小区i的信道之间的最小间隔,矩阵中的非对角元素Cij(i¹j)表示分配给小区i中的信道与小区j中的信道的最小间隔。每个小区频率需求数用矩阵来表示,其中矩阵R中的元素ri表示第i个小区的频点需求数,可用的频点集合为,其中FNum=max{fij},设fik为给第i个小区的第k个位置分配的频点,fik取值为正整数,fjl同理,它们之间应满足,目标函数的适应度S(F)定义为信道分配方案F违反约束条件的总数量,Fikjl描述fik与fjl是否满足约束条件Cij,数学模型如下:即在给定的C、R和可用频点集合FN,找到使目标函数S(F)值最小即为0的信道分配方案F。信道分配方案F采用最小间隔实数编码方式,F是一个N´rmax的矩阵,即:式中rmax是需求向量R的最大值,,表示将频点χ分配给第i个小区的第j个位置,当时,fij=0。3基于概率pi的新蜜源搜索算法在人工蜂群算法中蜂群主要有引领峰、跟随蜂和侦查蜂,一个蜜源位置(θi)与一个引领蜂(ei)相对应,ei先出去寻找蜜源位置θi,跟随蜂(oi)在舞蹈区等待ei带回蜜源的相关信息,等到ei回到舞蹈区后,oi根据ei的舞蹈得知θi信息,采用公式(4)以概率Pi选择一个θi,并在其邻域内采用公式(5)搜索新蜜源,比较蜜源θi和在其领域内搜索的新蜜源,选择较好的蜜源采蜜。在迭代过程中,若某个oi在设定的搜索次数内没有获得更好的蜜源,ei便放弃该θi,同时成为侦查蜂。并随机搜索新蜜源。令蜂群数量为M,第t次迭代之后,现有的蜜源位置集合为M,ei在该次搜索之后,获得的蜜源收益度为H(θi(t)),oi选择θi(t)的概率为:oi以概率Pi选择θi(t)之后,在其邻域内选择一个新的蜜源(θi(t+1))进行访问,选择的方法为:其中ψi为随机产生的步长。如果H(θi(t+1))>H(θi(t)),则用θi(t+1)更蜜源θi(t),否则θi(t)不变。若在连续的Limt次迭代之后,均不能发现更优的蜜源,则ei放弃该θi,同时成为侦查蜂随机搜索新蜜源。4改进的手动集群算法4.1迭代次数优化人工蜂群算法中,跟随蜂在选中的蜜源邻域范围内按式(5)搜索新蜜源,搜索步长具有随机性,算法寻优速度相对较慢,易陷入局部最优或易错过全局最优解。本文根据文献的研究成果,在实验数据的基础上将随机产生的步长改为随迭代次数动态变化的步长,不仅提高了算法的搜索精度,还能较好地平衡局部与全局搜索能力,如式(6)所示:其中,tmax为最大迭代次数;θmax(t)为第t次迭代的最优蜜源位置;0.5(1-t/tmax)是邻域搜索步长的动态权值,它随迭代次数的增加线性减小。该动态权值在算法初期有较大的值,使跟随蜂有较强的全局搜索能力,加快算法收敛速度;在算法后期随迭代次数的增加有较小的值,使跟随蜂有较强的开发能力并增强了算法的搜索精度,从而使蜂群在全局搜索和局部搜索之间达到动态平衡。4.2自由或c为了提高种群的多样性和算法的收敛速度,引入了选择性变异技术。选择性变异技术是一种单个体进化的方法,在信道分配问题中首先对待变异的个体计算适应度值S(F),即公式(1)的值。若S(F)>0,则遍历该个体解F中的每一个频点fij,用公式(2)进行分析,考察该频点fij是否对其他小区产生干扰。如果不产生干扰,则什么也不做;如果产生干扰,则需要对该频点fij进行变异替换。替换频点fij的频点必须满足第i个小区的共地约束(CSC),即Cii,同时还必须与前PCell个具有较大分配难度的小区满足兼容矩阵所要求的邻频约束(ACC)和同频约束(CCC)。分配难度deg计算公式为:5频域分配算法和步骤5.1基于2.2目标函数的多通道分配算法一个蜜源位置θi与一个信道分配方案Fi相对应,蜜源收益度H(θi)代表该蜜源相对应的信道分配方案Fi的质量,H(θi)越大相应的Fi违反约束条件的频点数越少,即解越接近最优解。具体关系见公式(8)。最大收益度与最佳信道分配方案相对应,搜索最佳蜜源的快慢代表寻找最佳信道分配方案的速度,即算法收敛速度的快慢。公式(8)中S(Fi)见公式(1)。在信道分配模型中目标是找到最小值,即找到使目标函数S(F)=0的信道分配方案F,该信道分配方案中没有违反干扰约束条件的频点;在改进蜂群算法中目标是求最大值,即蜜源的收益度H(θi)的最大值。信道分配目标函数S(F)的值越小,蜜源收益度值H(θi)越大,当S(F)为最小值等于0时,蜜源收益度H(θi)达到最大值。因此在改进蜂群算法中,求解最大收益度和信道分配方案中的寻找S(F)=0的最佳信道分配方案是相对应的。5.2采蜜、分级回归步骤1确定蜂群规模M,最大迭代次数tmax,可用频点总数FNum、PCell、Limt的值,引领蜂个数与跟随蜂个数相等,等于M。步骤2初始化M个可行解,计算初始化后的各个可行解的适应度S(F)和各个可行解所对应的蜜源收益度H(θi),并记录全局最优解θmaxx(收益度H(θi)最大或适应度S(F)最小)。若初始解中有S(F)=0的解,结束算法并输出S(F)=0的信道分配方案,否则执行下一步。步骤3模拟蜂群行为,oi根据ei的舞蹈得知θi信息,用公式(4)以概率Pi选择一个θi(t),并在其邻域内用公式(6)搜索新蜜源θi(t+1)。步骤4比较蜜源θi(t)和θi(t+1)收益度,选择蜜源收益度大的进行采蜜。步骤5对步骤4选中的蜜源进行3.2节的选择性变异。计算变异后的蜜源的收益,若此次变异产生的蜜源收益度大于变异之前的蜜源收益度,则接受此次变异,否则沿用变异之前选中的蜜源。步骤6若某些引领蜂对应的蜜源(解)收益度在Limt次循环后都没有改进,则放弃该蜜源,同时引领蜂转变为侦察蜂随机搜索一个新蜜源取代该蜜源。计算本次迭代全局最优解θmax,与上一次迭代的全局最优解比较,选择收益度大的作为本次迭代的全局最优解。步骤7计算所有蜜源的收益度H(θi)和蜜源相对应可行解的适应度S(F),若有S(F)=0,即蜜源收益度达到最大值,则结束运算并输出S(F)=0的信道分配方案;否则跳转到步骤3进入下一次迭代。步骤8若达到最大迭代次数都没有找到使S(F)=0的最佳信道分配方案,则结束运算,并认为算法不收敛。6仿真结果与分析算法用MATLAB7.0进行仿真,频率分配方案采用实数最小间隔编码方式,种群个数M=35,引领蜂个数=跟随蜂个数=M,算法循环总代数tmax=200,Limt=6,PCell=5;对文献的21小区系统进行频率分配,可用频率总数FNum分别取55、65、70、80、90,每种可用频点数各运行50次。图1为本文算法在采用可用频点数为55的收敛代数仿真图,图1中横坐标t为算法迭代次数,纵坐标为适应度函数S(F)的最小值,即信道分配方案F违反约束条件的总数量的最小值。表1为本文算法与文献算法的比较结果;表2为人工蜂群算法与本文算法比较结果。由图1可以看出,在可用频点数不充足为55的情况下,算法也有着较快的收敛速度,仅用17次迭代即可收敛。从表1的实验结果中看出,当可用频点数设为70时,文献只有90%的收敛率,而本文算法能达到100%的收敛率,且平均收敛代数在3.8代;同时应用到65和55个可用频点数中,文献不收敛,而本文算法的收敛率仍能达到100%,且平均收敛代数也只为5.4代和18代,可用频点为55的仿真结果如图1所示。这表明改进后的人工蜂群算法在频率分配上的效果优于传统的微正则退火算法。从表2的结果中可用看出,在频点数充足且相同的情况下,改进的人工蜂群算法的收敛代数在各可用频点的情况下均小于基本人工蜂群算的收敛代数,并且当频点数为65和55时,基本人工蜂群算法不收敛,而本文算法的收敛率为100%。用本文算法去处理文献的信道分配问题时,仅用1次迭