勇法
研绘
一种基于改进遗传算法的
资源分配策略
‘
张敏①党安红②王河媛①西安工业学院计算机科学与工程学院西安①北京大学电子学系北京
川
②
摘要提出一种基于改进遗传算法的整体优化的动态资源分配方案首先根据信道分配的特点构造了基因
链模型进而建立了一种整体优化模型该算法尽童保证最大程度的紧致分配同时针对遗传算法爬山能力差的弱点提出一种自适应遗传方法分析和仿真表明该方案与现有的和方案相比有较小的呼队率和较高
的频语利用率不论在业务童较大还是较小都能取得较好的性能指标关祖词信道分配蜂窝移动通信遗传算
法
引言
高速增长的移动通信系统的规模和对高速多媒
体通信的需求使得可供分配的无线频谱资源变得越来越有限而良好的信道分配是解决问题的有效
的措施之一〔‘,目前国内外学者大多致力于动态信道分配方案的研究〕但是若不采用其
他优化措施则仅当业务量较低时动态信道分配方
式才有较低的呼阻率〔‘幻许多“启发式算法用来
解决这个问题近几年神经网络技术图模拟退火思想困等在这方面得到了应用但是前者容易陷人
局部优化后者尽管可以达到全局优化但其实现过于复杂
遗传算法〕是近些年来迅速发展的一种
优化算法其首先由美国大学的教授提出此后为众多研究人员所注目本文从信道分配的特点出发将该问题抽象为优化问题同时针对’爬山能力弱的特点构造了一种自适应算法按照自适应交换率选择态个体进行交换操作同时按照自适应变异率选择个体进行变异操作
动态信道问题之遗传算法表征及适值函数的构造遗传算法不能直接处理动态信道分配间题中的参数所以必须把信道分配问题转换成由基因按一定结构组成的染色体假定一个蜂窝系统中共有个小区可用的信道总数为这样一个小区
所分配的信道数的变化范围为一当然具体的分配情况要受到许多约束条件〔‘〕这样可将一个小区的信道使用情况用位二
进制表示共有种状态可以将之映射为一位
的一维向量即‘一甜
式中表示第个小区的第个信道的分配情况若个信道被分配给第小区则其值为否则为因此整个系统的信道分配情况映射为一
,
位的一维向量结构形式如下二,,…,一‘‘…,…,,…
,
上式共有种状态每一状态对应一条基因链码遗传算法在进化搜索中是以适值函数为依据
的〔“〕而良好的信道分配就是在不违背其限制条件的基础上以紧缩模式排列信道满足更多用户的需要保证系统有较低的呼阻率〔‘浏在本文中为了达到整系统全局优化提出下面的命题
定理将所有的信道排队记为……,在不违背限制条件的情况下如果一条
基因链码中各元素的加权和即艺艺达到最大那么该基因链码对应的信道分配必然使服务区
正在使用的信道数达到最少其中是一常数
证明仍然假定系统共有个小区信道总数
为这样可以将对系统的某一个信道分配方案映射为维空间中的一个点设方案是由该命题得到的一种分配方案其中信道…的使用次数分别为…且鉴鉴…鉴为了证明是一最佳方案采用反证法假定方案为一更佳策略方案中信道…的使用次数分别为…且不
失一般性仍然有鉴鉴…因为某时刻系统中总的呼叫次数一定则
基金项目国家高技术基金资助“枷二
…二
以场年布移常
期
乡已线电通佑技术码求出相应的选择操作
选择操作是建立在群体中个体的适应度评估
的
基础上本文采用赌轮选择方式阁记群体中某个体的适应度为二则某个个体被选择的概率为
尸、习二
显然个体适应度越大则被选择的概率就越高反之亦然这样就可以决定那些个体被选出交叉操作
交叉算子是遗传算法中最重要的遗传操作本
文提出以下的自适应交叉概率在群体中选择个体进行交叉操
作
只了漏一了漏一〕︸一
象居研穷
一若方案与不同那么在信道一中至少有两个信道的次数不等假定为第与第个信道且续而,二衫其中尹由式存在以下情况
①若你,则由方案的含义知该方案中权值为的信道的使用达到最大化若
、则中信道的使用必然违背了信道分配原则所以这种情况不可能②若、则又由假设知簇你这样若说明在方案中权值较高的信道并未达到最大程度的复用所以方案也不可能是一更佳的方案
综上所述必然有、‘类似地
可以证明多个信道使用次数不同的情况所以与
为探空间的同一个点因此满足定理条件的方案为一最佳方案另一方面在实现优化紧缩模式时要受到一些约束条件主要是信道复用条件及每个小区需要的信道数可构造函数探万
”不干补凡‘“不于爷萨六十刀寻
一巩
一
尺
式中是常数是一个函数主要是约束同道干扰当小区与小区相互千扰时其值为否则为入代表邻道干扰限制函数当一簇其
取值为零其他情况则为‘为小区所需的信道数目综上所述得到适值函数如下
‘孟不孙刀不干补幼…、‘十“
不子笋
甲户沁
艺万礼一‘】’
基于自适应遗传算法的分配策略
为了叙述方便首先定义个函数即
和前者产生在「内服从均匀分布的一个整数后者则产生在【〕内服从均匀分布的一个整数
初始群体的生成由前面的假设知系统总的信道需求为二
艺‘在初始群体的形成中提出以概率
,
二一二。…其中。‘分匕决定链码中信道的取值
艺
情况这样有利于提高收敛率群体的规模将影响遗传优化的最终结果以及遗传算法的执行速率在该文中假定产生犯个个体然后对每一个个体解
式中人是群体中的最大适值度分别是交换串中的较大适值度及群体的平均适值度是小于的常数一般取值比较大
根据信道分配间题的特点在进行交叉操作时按以下步骤进行①交叉与否若交叉转叭否则不交叉转变异操
作
②调用函数决定将在哪一个蜂窝小区进行交叉操作
③调用函数决定将具体在哪一处进行交叉处理④没有选中的小区直接传给后代而对选中的小区将交叉点后的两个体的部分进行互换生成新
的个体
变异操作
变异操作的基本内容时对群体中的个体串的某些基因作变动在文中给出以下变异概率进行变异操作
一”。‘赢
一几瑞一几妻
凡几式中气几似是群体中的最大适值度几是变异串的适值度尸。,是小于的常数一般取值比较小首先调用函数决定变异与否若变异则调用函数决定变异的位置并将变异位置的值
取反一般说变异概率都很小否则接近最优解的基因链会引变异而遭到破坏优化方案判断经以上一产生了新一代群体对新的一组信道分配值进行评价求出其适值函数值然后
以娜算法研穷重复一形成孙子代不断地迭代其结果就
会收敛那么收敛的解就是最后要求的解也就是欲
求的一个优化的信道分配方案
方案仿真
仿真模型如图所示它包括个小区所有小区
的形状和大小均相同信
道
的复用模式为设
小区到
达的呼叫符合泊松分布呼
叫持续时间满足均值为
秒的负指数分布验证当业务量增加时蜂窝的呼阻率情况图是将
本文方案与固定信道分配方案以及动态信道分配
结论本文提出一种基于改进遗传算法的优化动态信道分配方案文中基于信道分配与遗传算法各自的特点构造了遗传算法的信道分配实现方案根据信道分配的优化原则给出一个定理为了克服遗传算法爬山能力差的弱点提出一种自适应遗传方法该方案与现有的和方案相比有较小的呼阻率和较高的频谱利用率不论在业务量较大还是较小都能取得较好的性能指标
图仿真蜂窝系统示意方案比较可以看出无论在话务量较低还是较大时采用以方案系统性能都有很大的改善注意图中横坐标是业务量的增加量而不是业务量的大小「一
一
一一—
一
十一
一一
一一八
图业务业务童增加黄与呼队率
参考文献川殊缨
叮
脚浏
匆、〔」党安红朱世华程江模块化分类紧致的信道分配方案及性能分析电子学报一〔〕凡如汕
。
。铡石朋】
明一们川月
。
胃全加
一〔〕
党安红朱世华汤俊雄蜂窝移动通信系统中的
一种分
级紧致的动态信道分配方案通信学报加
〕加职一二
咫一〕。儿
服川
面
勿一〕颤
耐
呵
,一
一上接第
页
结论本文将动码与高阶正交幅度调制相结合提出了具有较高频谱效率的联合编码调制方案采
用软解调的方式将编码及调制后经过信道传输的符号转换成对应的概率信息并作
为
译码器的输人从而获得了较高的系统性能
高斯信道以及瑞利衰落信道下的仿真结果都显示了
该方案的纠错能力接近于基于。码的联合编码调制系统然而和本文所提出的方案相比后者由于采用了复杂的或一算法译码复
杂度大大增加
着重研究了采用码的高频谱效率编码调制系统的设计和相关算法并比较了采用不同编码长度系统的抗噪性能从理论上分析优化码的结构包括采用纠错能力更强的非规则结构的码应能明显的提高系统的性能这些是将来
需要进一步研究的课题
参考文
献
〔助一一加玩
邸翻
幻佣一雌
瑰而
一〔卿
助
一一
仃
即哪肠
一一
脱,
自
〔〕俪“
一玩沈司
伽曰
田”知肠
助肠印
叮
朔叨一晰
任而
一
声姗功玩卜佣。幻
麟
以鸿年分今布
期
无线电绳借执术