自动分配算法（通用7篇）
自动分配算法 篇1
在物流控制系统中自动化立体仓库的出现不仅彻底改变了仓储行业劳动密集、效率低下的落后面貌,并且大大拓展了仓库功能,使之从单纯的保管型向综合的流通型方向发展。目前随着电子数据交换技术的发展及应用,自动化立体仓库系统逐步向3I(Intelligent,Integrated,Information)仓库系统过渡。而一个自动化立体仓库效率的高低主要取决于库区和货位的分配策略,使用好的优化策略能大大提高出入库频率、方便盘库和移库操作。对巷道两侧货架上的货物进行存取操作,一般有单元出/入库和拣选出/入库两种作业方式[1]。本文主要讨论单元出/入库作业方式的货位优化问题。
通过对立体仓库的库区和货位采用合理的分配控制策略,提高自动化立体仓库的工作效率,一直是一个热点问题,对自动化立体仓库货位分配控制策略的优化算法的研究也在不断深入。解决这类问题的优化算法包括迭代计算法、枚举法、随机算法、遗传算法等。本文提出了一种改进的解决多目标优化问题的Pareto遗传算法解决货位优化问题,可以有效地解决自动化立体仓库的货位优化分配问题。
1 自动化立体仓库货位分配控制策略
为提高自动化立体仓库的效率和方便货位管理,自动化立体仓库货位分配控制策略常用的有如下几个:
(1)改进的先进先出。采用改进的先进先出原则,若检验合格的有效期为12个月,那么将库存时间在1~12个月的货物严格按照入库时间的先后进行出库操作,不足一个月的货物忽略先进先出原则,按照距离就近的原则进行操作,提高出库效率。
(2)上轻下重。进行入库操作时,重物应放在仓库的下部货架,轻的放在上部的货架,使货架受力稳定。
(3)分巷道存放。当仓库有多个巷道时同种货物要分散存放在不同巷道。
(4)货物相关性。相关性大的货物往往同时出库,所以应该尽可能放在相邻位置。
(5)货位分区。根据货物出入库频率和特性,将立体仓库划区分段。
(6)最短路线。对于出入库操作,找到货物所在的货位分区后,按照距离出入库台最近的货位作为出入库的货位[2,3]。
本文在总结了当前货位分配优化策略的基础上,提出了一种新的货位优化的方法。该方法首先将货架进行扇形分区,即将存储货物进行分类;然后在每一库区中按照货位分配策略,采用改进遗传算法进行货位优化,这样更加有利于立体仓库的货物管理。
2 库区优化分配问题
2.1 库区分配优化问题的数学模型
库区分配优化问题是一个典型的指派问题。这是一类特殊的线性规划问题。在进行货位分区时,我们作如下假设:货物的存放种类已知;每种货物单位时间内存放的数量已知;每一种货物的存取频率已知。
由此本文提出以下的控制策略。
Step1:将货物按照出入库频率和质量分类,其数目等于仓库分区的数目。
Step2:根据货物的分类数,将货架进行扇形分区。其中表1描述了一个8列4层的货架分为4个库区的扇形分区情况。综合考虑货物的需求频度和质量,可以将货物表述为n种类型,用p表示质量和需求频度,p=!0,1,2,…,n",分别表示质量和需求频度依次变小。按由大到小进行排序,进行划分形成优先级不同的库区。在此表中p值相同的货位合成为一个库区,p越大代表库区的优先级越低,距离出入库台最远。
Step3:根据堆垛机取放某种货物的工作量建立权值矩阵,单位时间内堆垛机取放某种货物的工作量与该货物的出入库频率、货物的质量和该货物存放的位置有关,将该货物的出入库频率乘以质量再乘以堆垛机运行至货物存放位置所在库区的单位能量消耗因子作为权值因子[4],即:
式中,K为比例因子,取1-1.5;fi为i种货物的出入库频率;Mi为i种货物的质量;G为重力加速度;hj为堆垛机从原点到j区的单位能量消耗因子。
经过以上处理,将建立数学模型如下:
式中,xij=0或者1;i,j=1,2,…,n,xij=0表示为j区放入i类货物。
Step4:经过Step3得到的分区可能部分小区的货位数不能满足实际的需要。则要进行修正,修正的原则是“就近取多补少”,也就是说如果某个区的货位数较少,则从相邻的库区取货。
2.2 遗传算法求解库区分配的优化问题
遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法,目前遗传算法在解决组合优化问题时,操作简便、鲁棒性强,因此在解决指派问题中得到了广泛应用[5]。本文构造了求解该问题的遗传算法。
(1)编码。在本文中编码采用顺序表达法。其意义举例如下:设某仓库分为6个区存放6类货物,用顺序表达法时某个个体为[135246],该个体表示第1个库区放第1类货物,第2个库区放第3类货物。依次类推。
(2)构造适应度函数。
Qmax为按式(4)计算当代中目标函数的最大值,Q为目标函数值。
(3)初始种群的产生。随机建立有n个元素的数组(n为库区的个数),其中该数组中的元素互不相同。
(4)选择操作。在选择操作中采用轮盘赌机制。
(5)交叉操作。首先是任何在双亲中指派到相同位置的货物在后代中仍占据这个位置,然后对于剩下的位置从双亲中指派到该位置的两类货物中随机选一类货物,要按照从左到右的顺序进行。最后将剩下的未指派的货物分派给尚空闲的位置。
(6)变异操作。采用逆变异,即随机选择某个体两个位置,并将两点间的顺序交换。
3 货位分配优化策略
货位分配的主要目标是处理任意调度货物时,最大限度地缩短行走时间。首先对货架进行扇形分区,通过遗传算法实现库区进行优化分配。然后在货物找到相应的库区后按照货位优化策略寻找最优货位。
3.1 货位分配优化问题的数学模型
按照上述的货物分配策略建立如下的数学模型。假设:某仓库货架共有p列q层,处于第i列j层的货位记为(i,j)(i=1,…,p;j=1,…,q),出库台的位置记为(0,1)。不失一般性,设各货位的长度及货箱的质量相同,则固定货架的货位分配优化问题可以描述为:
式中:xij=0或者1;i=1,2,…,p,j=1,2,…,q;mij,nij为第i列j层货位上单位货物的质量和该货位货物数量;Vx和Vy为堆垛机的水平和垂直运行速度;L为货位的长度;H为货位的高度;a为货物的总数量。
上述模型中,式(6)依据货位分配策略中上轻下重的原则。即进行入库操作时,重物应放在仓库中的下部货架,轻的放在上部的货架,使货架受力稳定。式(7)依据货位分配策略中的最短路线原则。即对于出/入库操作,找到货物所在的货位分区后,将离出入库台最近的货位作为出库货位。式(8)为在不考虑堆垛机启动和制动的情况下,将第i列第j层货位上的货物搬运到出入库台所用的时间。
3.2 Pareto遗传算法求解货位配置优化问题
货位的分配需要同时考虑货架稳定性和出入库效率,这是一个多个目标函数的优化问题。本文将Pareto最优解的概念与遗传算法相结合,提出了一种改进的解决多目标优化问题的Pareto遗传算法[6]。通常的多目标优化问题大多都有很多个Pareto最优解。传统的GA在遗传操作中包括三个算子:选择、交叉、变异[7]。Pareto GA在此基础上还有小生境技术、Pareto解集过滤器和精英保存三个算子。其主要运算过程如下:
(1)编码。根据货位的特点,采用p×q矩阵对解进行编码,如果矩阵的第i行j列位置的元素为m,则表示编号为m的货物放在货架的第(q+1-i)层j列上。
(2)计算适应度值。适应度值为当代中两个目标函数的最大值减去该个体的目标函数值。
(3)选择算子。选择算子之前要对群体进行并列选择过程和群体分级操作。并列选择过程:将整个群体均等地划分为两个子群体,分别在两个目标函数的相应子群体中产生数量相同的两个子种群。群体分级:为了得到最优解,在进行选择运算之前,需要根据个体的非劣解水平将种群分级。具体实现方法为:将种群中的所有非劣解个体划分为同一级,并赋予等级为1。重复上述过程,直到种群中所有个体都被赋予相应的级别为止。在选择过程中,第i级的点的选择概率可以由下式确定:
式中,M为群体规模,Nr为群体分级数,Psi为第i级的群体规模,Fi为第i级点的选择概率。
(4)交叉操作。在遗传算法中,通常随机选择两个个体进行交叉操作。针对论文提出的多目标优化问题,引入了交配限制策略[1]。只有当两个个体不在同一群体时,才能进行交叉操作。按照这种方式,不同目标函数下的优良基因可以进行充分组合,能以较大的概率找到各个目标性能均较好的折衷解。根据货位优化配置问题的目标函数值直接取决于货物在货架上的位置,交叉操作中采用了部分匹配交叉算法。
(5)变异操作。变异算子依概率选择一部分个体实施变异,随机选择两个货位,把这两个货位上的货物进行对换。
(6)小生境技术。为了保证寻优过程不收敛于可行域的某一局部,使种群向均匀分布于Pareto前沿面的方向进化,需要通过共享函数定义一小生境加以实现。然后对种群中聚集成小块的个体施加惩罚,使其适应度值减小。
(7)精英保存策略。为保留种群进化过程中出现的最优个体,将父代种群和子代种群合并为一个种群,对该种群中的个体进行群体排序和共享函数惩罚。然后根据非劣点级别的高低、共享后个体适应度的高低,将种群中靠前的50%个体作为新的种群进行下一轮进化。采用上述技术和策略的遗传算法不仅可以收敛于多目标优化问题的Pareto解,而且可以保证其分布较为均匀[8]。
(8)Pareto解集过滤器。其作用是将每一代中的非劣点保留下来,同时去掉解集中的劣点。每一代中级别定为1的点都放入Pareto过滤器。Pareto解集的规模可以任意设定。当新点的数量超过规定的Pareto解集的规模时,再进行一次排序,剔除掉其中的劣点。如果剩下的非劣点的数量仍超过Pareto解集的规模,再删除那些与其它点距离最近的点。
3.3 改进的解决多目标优化问题的Pareto遗传算法步骤
Step1:随机生成初始种群并确定最大允许进化代数Gmax,确定初始种群规模n1;
Step2:构造适应度函数并计算各点的适应度;
Step3:利用非劣点的定义对群体分级;
Step4:进行遗传操作:选择、交叉、变异、小生境,生成新群体;
Step5:依据这2M个个体的新适应度对各个个体进行降序排序,记忆前M个个体;
Step6:取出级别为1的点,放进Pareto解集过滤器;
Step7:判断t是否小于Gmax,若满足,则转向步骤2,若不满足,则终止,输出最优解集。
4 仿真实验及分析
仿真实例为12层40列仓库,立体仓库的货架参数货位长度L=120cm,货位高度H=80cm。堆垛机的水平运行速度Vx=3m/s,垂直运行速度Vy=1m/s。货位被划分成A、B、C、D、E共5个区域。各类货物的参数如表2。
在表2中,第二列表示货物编号为1的1类货物所需要的货位数为95个,其作业概率为30%,货物质量为60kg/个。依次类推,已知每种货物所需要的货位数、作业概率和货物的质量,通过用C语言编写库区分配的优化程序,可以得到该类货物存放的库区号。仿真结果为3类货物存放在A区,1类货物存放在B区,5类货物存放在C区,2类货物存放在D区,4类货物存放在E区。货物质量越大、出入库频率越高表示货物存放在货架低层、离出入口越近的货位上的可能性越大。剩余的货位填充到每个小区末尾,作为备用货位,以防临时增加该区物料或方便以后盘库。按照出库频率高的库区对应优先级高的货位区的原则,用遗传算法找到某类货物的库区,然后在对应的库区用Pareto最优解集进行计算,使货位得以合理分配。
仿真实验中,对该仓库进行货位优化分配时取种群规模pop=100,交叉概率Pc=0.8,变异概率Pm=0.2,最大允许进化代数Gmax=300,Pareto解集过滤器的解集规模为100。
按照货物的出入库频率做以下假设:共有100个货物要进行出入库操作,其中1类货物和3类货物各30个,2类和4类货物各10个,5类货物20个。若按照传统的顺次排放策略,S=23 180kg,T=1 133s。采用上述算法分配货位,可以为用户提供多个Pareto最优解,用户可根据货架的承重能力和仓库的实际运行情况确定最终解。我们选择其中一组解进行实验验证得到S=20 950kg,T=987.2s。由此结果看出在降低货架重心的同时,总体出入库效率有较大幅度的提高,提高了自动化立体仓库的存取效率。优化后的货位的分布图如图1所示。该图中颜色最深的小方框表示在此位置存放了货物。颜色的深浅代表了不同的库区。
5 结论
本文重点讨论研究了立体仓库库区和货位的分配优化策略,提出立体仓库的库区优化数学模型。在库区优化基础上,提出货位优化数学模型,对采用改进遗传算法Pareto GA解决货位优化问题进行了分析。其中在库区优化控制策略中,我们在建立数学模型时综合考虑了货物的质量和出入库频率,将货物按照出入库频率和质量分类,根据货物的分类编号,将货架进行扇形分区。货物按质量和需求频度由大到小进行排序形成不同的优先级对应于优先级不同的库区,部分小区的货位数不能满足实际的需要的,按照“就近取多补少”原则进行修正;在货位优化控制策略中,我们同时考虑了货架稳定性和出入库频率,这是一个多个目标函数的优化问题,在本文提出的方案中采用Pareto最优解的概念与遗传算法相结合的改进算法,其涉及群体分级、小生境技术、Pareto解集过滤器和精英保存技术。
通过仿真实验及分析可以看出本文提出的采用改进遗传算法优化策略可以有效地解决自动化立体仓库的货位分配问题,提高了出入库操作的执行效率。
参考文献
[1]商允伟,裘聿皇,刘长有.自动化仓库货位分配优化问题研究[J].计算机工程与应用,2004(26):16-18.
[2]柳赛男,柯映林,李江雄,等.基于调度策略的自动化仓库系统优化问题研究[J].计算机集成制造系统,2006,12(9):1438-1443.
[3]E Zitzler,L Thiele.Multiobjective evolutionary algorithm a comparative case study and the strength Pareto approach[J].IEEE Trans on Evolutionary Computation,1999,3(4):257-271.
[4]银光球,何福英.自动化立体仓库中库位优化模型研究[J].福建工程学院学报,2006,4(3):347-351.
[5]周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,1999.
[6]Carlos F M,Peter F J.An overview of evolutionary algorithms in multiobjective optimization[J].Evolutionary Computation,1995,3(1):1-16.
[7]赵振华,王杰,娄春元.基于遗传算法的带时间窗约束车辆路径问题研究[J].物流科技,2007(2):92-95.
[8]费烨,李楠楠,韩泽光.基于Pareto解集的多目标优化方法及其应用[J].起重运输机械,2006(9):13-15.
基于差值分配的信道分配算法研究 篇2
MF-TDMA是一种频分多址 ( FDMA) 和时分多址( TDMA) 相结合的二维多址方式[1,2,3]。MF-TDMA将信道分割成频率不同的若干个载波,按时间在每个载波上划分不同的时隙。信道资源分配算法采取相应的策略选择合适的载波,并在载波上分配时隙资源给地球站发送数据。而高效的信道资源分配算法和用户服务质量的保证一直以来都是MF-TDMA资源管理技术的重点[4,5]。
MF-TDMA卫星通信网络中信道时隙资源分配一般采取较为高效的申请分配机制[6,7],该机制是地球站根据实际业务需求发送业务带宽申请,中心站接收业务申请并根据申请为其分配带宽资源供地球站发送数据,在业务带宽分配过程中主要考虑如何保证业务的服务质量[8]。卫星通信系统中传输的业务按实时性可以划分为实时业务和非实时业务。非实时业务主要包括传真和IP数据等,对时延要求不高,时延对非实时业务的传输影响不大。实时业务主要包括话音和视频等,而它对时延、抖动等具有较高的要求,对时延非常敏感,它要求带宽分配结果不存在时延或时延非常低,才可以确保实时业务的正常通信,保证其服务质量。因此,如何消除实时业务抖动时延,降低呼叫掉线率,提高实时业务的服务质量,是本文研究的重点。对此,在周期轮询信道分配算法的基础上提出了差值分配算法,将业务带宽申请分为固定部分和变化部分,对2部分采取不同的信道分配策略,以减少实时业务的掉线现象,提高用户的业务满意度。
1分配约束条件
MF-TDMA系统的信道时隙资源分配问题的本质[9]是在一定的约束条件下,按照一定的原则,针对业务本身特性和所需时隙数量,在信道中寻找符合条件的空闲时隙进行分配。
目前对于MF-TDMA卫星通信系统,时隙资源分配问题的约束条件[10,11,12]主要有:
1同一地球站分配的时隙数量不能超过一个载波的时隙容量;
2一个地球站在一次业务连接中使用的时隙可以是连续的也可以是分散的;
3同一地球站分配的时隙资源,在时间上不能重叠;
4为避免冲突,同一个时隙资源不能同时分配给2个业务申请。
时隙分配最基本原则为: 某个站在某一时刻只能在一个载波上发送。这也是MF-TDMA体制的基本原理所决定的。
2周期轮询法
2. 1分配原理
周期轮询[13]算法的分配原理是中心站接收到各地球站的时隙申请信息后,按照申请业务的优先级,将其从高到低进行排序; 然后,按照一定的顺序依次提取业务申请,找到适合的载波,从头至尾进行一次轮询,检测时隙是否空闲,如果空闲,检测该时隙是否发生冲突,如果未发生冲突,直接将该申请分配,提取下一个申请,如果发生冲突,继续检测下一个时隙,直至整个载波全部轮询完毕; 该申请的带宽没有全部满足则无法被分配,直接放弃,前面已分配的部分该申请释放,提取下一个申请,从载波起始位置继续重复轮询过程。
2. 2算法性能分析
随着系统网络规模的扩大,每一个分配周期地球站的申请量远远超过信道的容量。每次分配信道时都要重新分配,这可能使得上一帧已分配的实时业务在当前不能分配,实时业务服务中断,增加了掉线率,降低了实时业务的服务质量。
因此,为了保障实时业务的服务质量,降低实时业务的掉线率,提出了差值分配算法。该算法对载波时隙表进行维护,对实时业务申请带宽变化的部分进行动态的分配调整,非实时业务进行周期轮询重新分配。
3差值分配
3. 1分配原理
差值分配算法原理是: 在地球站根据时隙分配表进行数据的发送后,不再将信道中的所有分配时隙收回,而是根据上一帧的实时信道分配情况和实时业务的时隙申请二者取差值,差值为零,说明实时业务申请带宽需求没有变化,最大限度地保持已经分配的实时业务申请时隙资源位置不变动; 带宽需求减小的业务,将多余的时隙释放; 带宽需求增大的业务,对已分配的时隙位置最大限度地保持不变,对增加的带宽需求进行轮询分配,在信道中搜索空闲时隙,如果无法满足全部带宽,将该实时业务的所有时隙全部释放,业务被拒绝。同时非实时业务,进行轮询,重新分配。
差值分配算法分配原则为: 针对变化的实时业务申请部分做动态调整分配,尽量保持上一帧已分配实时业务申请在下一帧中存在且分配的时隙位置尽量保持不变,同时对非实时业务进行轮询重新分配,最大限度地降低了实时业务的掉线率。
3. 2分配流程分析
该算法的流程如图1所示。
具体的分配步骤如下:
1对上一帧的各个地球站信道分配结果进行统计; 2接收当前帧的各地球站的业务时隙申请,由上一帧的统计结果和这一帧的时隙申请情况,得出每个地球站的实时业务申请分配差值; 3对于分配差值为零、业务带宽需求无变化的地球站不做操作; 如果时隙中分配的地球站的分配差值为负,将多余的时隙释放; 如果分配差值为正,在信道中搜索空闲时隙进行分配,分配的时隙个数与分配差值相等; 4非实时业务时隙申请采取轮询重新分配。
这一算法需要对上一帧的分配情况进行统计,在分配的过程中,业务持续时间结束会释放占用时隙为空闲时隙。对这些空闲时隙的位置等信息进行记录,在接下来的分配过程中可以直接对其进行占用,减少了系统对信道中空闲时隙的搜索操作,可以缩短信道分配时间。对业务对带宽需求变化的部分进行释放和分配,最大限度地保证了信道中实时业务时隙位置保持不变,以减少实时业务的时延降低掉线率。
4仿真结果分析
4. 1仿真模型
针对MF-TDMA系统,为了更好地验证实时业务的分配策略,网络规模较小时,业务总的时隙需求数量是小于信道容量的,随着网络内地球站数量的增加,最终时隙需求总数量大于信道容量。在此采用阻塞率与掉线率验证算法的性能。仿真条件设定如下:
1网络中的地球站规模[100,600];
2信道矩阵包含8个载波,每载波包含128个时隙;
3发出申请的地球站随机分布,业务申请满足泊松分布;
4每个业务要占用的时隙个数在 [1,8]范围内随机取整数,业务持续期间不发生变化。
阻塞率: 系统提供的信道数远比用户数要小得多,当用户要通信时,会发现所有信道可能全部处于繁忙状态,这种现象称为阻塞。业务带宽申请次数累加得到总申请数量Req Num,系业务申请未成功分配的数量Fail Num。阻塞率δ表示为未成功分配的申请数量与总的申请数量的比值,
掉线率: 反映了系统业务的通讯保持能力,是用户直接感受的重要性能指标。每个终端产生的呼叫次数累加得到总呼叫次数Call Num,每发生一次掉线,则累计掉线次数Drop Num。掉线率μ表示为掉线次数与总的呼叫次数的比值,
4. 2仿真结果分析
每次仿真在连续进行1 000次的信道分配,阻塞率与掉线率是这1 000次仿真统计的平均值。
实时业务的阻塞率如图2所示。图2中2条曲线分别表示周期轮询法和差值分配法阻塞率。
由图2可知,在网络规模较小的时候,业务数量较少,信道可以完全容纳,业务时隙申请不会受到拒绝,阻塞率为零。随着网络规模的增大,总的业务时隙申请数量超出了信道容量,出现了业务阻塞,并随着地球站数量增多呈上升趋势。周期轮询与差值法的阻塞率相似,2条曲线基本重合,二者拥有相似的阻塞率。
实时业务的掉线率如图3所示。图3中2条曲线分别表示周期轮询法和差值分配掉线率。
随着网络规模的增大,业务的时隙申请数量超出了信道时隙的大小,周期轮询法对实时业务的申请直接进行分配,不考虑上一帧的分配结果,这样的分配造成其较高的掉线率,并且随着地球站的数量增多呈上升趋势。差值分配法中如果对地球站的实时业务时隙申请进行分了配,那么在接下来实时业务的整个持续期间,时隙的位置尽量保持不变,始终能够保证实时业务的正常通信,在这种非常理想的情况下实时业务的掉线率为零。
5结束语
为了提高实时业务的服务质量,针对周期轮询信道分配算法实时业务掉线率较高的缺点,在该算法的基础上,提出了差值分配的算法。新算法对终端业务申请采取不同的分配策略,根据各终端连续2帧之间的实时业务申请的差值进行时隙资源的动态释放与分配,非实时业务进行重新分配,来减少实时业务的掉线现象。新算法进行仿真验证,仿真结果显示,差值分配和周期轮询算法具有相似的阻塞率,而新算法同时具有较低的掉线率,进而提高了实时业务的服务质量。
摘要：资源的高效利用与服务质量保证是多频时分多址(MF-TDMA)卫星通信系统正常运行的关键技术。通过对典型的周期轮询信道分配算法进行分析,针对该算法实时业务掉线率较高的缺点,提出了差值分配算法。新算法是在周期轮询信道分配算法的基础上,结合业务带宽需求动态变化的特点,将业务带宽申请分为固定部分与差值部分并分别采取不同的分配策略。仿真结果表明,新算法可以有效地降低实时业务的掉线率。
浅析TDMA时隙分配算法 篇3
关键词：TDMA,时隙分配,分配模型
在TDMA系统中, 时间被划分成了相互不重叠的时帧, 而时帧又被划分成了相互不重叠的时隙, 网络中各个节点在各个时隙内进行相应的操作。系统采用TDMA接入方式, 从而需要设计如何进行时隙分配, 即如何将时隙分配给网络中的各个节点, 从而使得在相邻节点之间传送分组时产生的冲突较小, 并且系统的吞吐量和空间复用性尽可能高。
1 时隙同步
网络采用TDMA方式接入信道, 首要条件便是网络中各个节点保持时隙同步。时隙同步一般可以分为3类:卫星授时同步方式, 主从同步方式和互同步方式[1]。卫星授时同步方式即是为网络中的每个节点配备能接收授时卫星信号的接收机, 通过卫星传输信号实现全网时间同步。主从同步方式即是网络中存在一个中心节点, 从而让网络中所有节点的时间与中心节点时间保持一致, 而互同步方式即是网络中的各个节点相互发送带有时间信息的数据分组进而调整自己的时钟从而逐步实现整个网络时隙同步。
2 TDMA协议中的时隙分配算法
在全网实现时隙同步之后, 需考虑的便是如何将时隙进行有效分配从而使系统获取较好的性能。研究TDMA协议最主要的是研究其时隙分配算法, 从目前的研究成果来看, 现有的时隙分配算法大致可以分为3类[2]:固定时隙分配算法、动态时隙分配算法和固定与动态相结合的混合时隙分配算法。其中, 根据算法的实现方式, 基于动态分配算法的TDMA协议又可以分为集中式和分布式;分布式动态TDMA协议还可依据时隙分配时是否需要拓扑信息从而再分为拓扑依赖和拓扑透明2种类型。协议分类如图1所示。
基于固定分配算法的TDMA协议将时间分割成时帧后, 每一帧都分成固定数目的时隙, 且每个节点分配的时隙都是唯一且固定的, 网络中的节点根据相应的算法使用时隙。比较有代表性的是启发式时隙分配算法、有序节点染色算法、均域退火算法和基于神经网络的时隙分配算法。
基于动态分配算法的TDMA协议是当节点需要发送数据时才给其分配所需时隙, 数据发送完毕后, 便不再将时隙分配给该节点。
集中式动态TDMA协议一般存在一个获知整个网络节点信息的中心控制节点, 该中心节点为整个网络中的节点进行时隙分配。具有代表性的便是集中式轮询协议[3]。
分布式动态TDMA协议不存在中心在控制节点, 网络中的各个节点通过交互信息对各自的传输时隙进行预留。
基于拓扑透明特性的分布式动态TDMA协议在为节点分配时隙时, 不需要考虑当前的局部网络拓扑信息。其中, 具有代表性的是Chlamtac等提出的扩时多址接入协议 (TSMA, Time Spread Multiple Access) [4]。
基于拓扑依赖特性的分布式动态TDMA协议在分配时隙时则需要考虑网络拓扑信息, 且根据是否需要提前收集领域信息又分为2类: (1) 是各个节点先通过交互控制信息来收集领域信息, 然后再根据收集的领域信息进行时隙分配, 其中比较有代表性的是统一时隙分配协议 (USAP, Unifying Slot Assignment Protocol) [5]和改进型协议USAP-MA (USAP Multiple Access) [6]。 (2) 通过控制包的交互, 直接解决领域内的冲突, 进行时隙预留, 其中具有代表性的是五步预留协议 (FPRP, Five-Phase Reservation Protocol) [7]。
基于混合分配算法的TDMA协议将时隙固定分配给对应的节点, 同时允许在不干扰该时隙使用节点的传输情况下其它节点可以对该时隙进行竞争。比较有代表性的有PTDMA协议、ABROAD协议[8]。
3 时隙分配模型
时隙分配模型是时隙分配算法的重要数学理论依据, 不同的时隙分配方案有着不同的时隙分配模型。以下分别介绍固定时隙分配模型和分布式动态时隙分配模型。
3.1 固定时隙分配模型
在固定时隙分配算法中, 时隙分配的目标是在系统中实现无冲突传输数据, 且时帧长度尽可能短, 信道利用率尽可能高。
设网络中节点数为n, 链路集合为E那么其连接矩阵R可以表示为:
其中,
上式表示如果节点i, j之间都可以直接收到对方发送的报文, 即链路e (i, j) ∈E存在, 则, 否则。
固定时隙分配算法要求每个节点在一个时帧中至少分配一个时隙, 因此设一个时帧由m个时隙组成, 则可以用矩阵S来表示一种时隙分配方案。
用表示节点i的信道利用率, 则整个网络的信道利用率可表示为:
在固定时隙分配算法中, 首先要保证一个节点在一个时帧中需至少分配一个时隙;其次为避免冲突, 间隔小于或等于两跳的邻节点间都必须分配不同的时隙。固定时隙分配算法的目标即是用最短的帧长度实现最高的信道利用率。
因此, 固定时隙分配问题模型为:
3.2 分布式动态时隙分配模型
在分布式动态时隙分配中, 单个节点无法获取整个系统节点信息, 因此在进行时隙分配时需要根据自身业务要求, 动态地进行时隙分配, 使得自身节点对其它节点的影响的最小, 同时使得节点业务传输性能最大。
设网络中需为节点i分配个时隙, 网络中节点总数为n, 一个时帧由m个时隙组成, 每个时隙的长度为τ, 同理可用矩阵S来表示一种时隙分配方案。
在进行时隙分配时, 如果给节点i和其它节点分配了相同的时隙, 则发生了时隙冲突。因此节点i在此次时隙分配中的时隙冲突概率可以表示为:
其中:
节点i的信道利用率表示为:
节点i的平均报文时延为:
在分布式动态时隙分配算法中, 只需保证对节点i分配的时隙数量至少满足其需求, 但目标即是要使冲突概率和时延最小, 同时使得信道利用率最高。
因此, 分布式动态时隙分配问题模型为:
4 结语
研究TDMA协议, 最主要的便是对其时隙分配算法进行研究。本文从内涵、现状、理论支撑上对TDMA时隙分配算法进行一定的分析、归纳和总结, 从而能使研究人员纵览该领域内的研究情况, 为其进一步深入研究打下重要基础。
参考文献
[1]董超, 田畅, 倪明放.Ad hoc网络时钟同步研究[J].通信学报, 2006 (9) .
[2]聂建耀, 许勇, 张金娟, 等.一种应用于Ad Hoc网络的改进型TDMA动态时隙分配算法[J].移动通信, 2008 (22) .
[3]曾勇, 黄巍, 杨静, 等.运用动态优先级轮询机制的数据链仿真[J].电子科技大学学报, 2008 (2) .
[4]Chlamtac I, Farago A.Making Transmission Schedules Immune to Topology Changes in Multihop Packet Radio Networks[J].IEEE/ACM Transactions on Networking, 1994 (1) .
[5]Young C D.USAP:A Unifying Dynamic Distributed Multichannel TDMA Slot Assingment Protocol[C].IEEE Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies, San Francisco, CA, USA, 1998.
[6]Young C D.USAP Multiple Access:Dynamic Resource Allocation for Mobile Multihop Multichannel Wireless Networking[C].IEEE Military Communications Conference, 1999.
[7]Zhu chenxi, Corson M S.A Five-Phase Reservation Protocol (FPRP) for Mobile Ad hoc networks[C].Wireless Networks, 2001
自动分配算法 篇4
在分布式计算、并行计算和网格计算逐步发展成熟的基础上,云计算应运而生。云计算的核心思想是将计算服务器、存储服务器 和宽带等 资源通过 网络连接,形成以 “云”形式统一管理,用户只需根据自身需求请求资源池资源,由云计算中心负责所有资源调度和管理,保证用户能够根据需要获取计算力、存储空间和各种软件服务[1]。
李伯虎院士[2]通过引入“云计算”理念,首先提出构建新网络化建模与仿真平台———“云仿真平台”。云仿真平台通过在虚拟机中部署仿真软件、服务、模型等资源组件, 为用户仿真需求提供相应的计算资源。类似于云计算服务模式,云仿真技术将仿真模型、仿真流程等资源接入到云计算环境中,通过仿真模型即服务或仿真流程即服务模式满足用户仿真需求[3]。
随着云计算网络的不断增大和仿真用户不断增多,如何及时、高效对云仿真资源进行调度,提高资源利用率,成为云仿真平台研究的核心问题之一。本文探讨基于遗传算法的云仿真平台资源服务调度技术。云计算服务中的资源调度技术日渐成为学者关注的焦点。针对仿真资源最优化问题,以往研究中提出了很多有价值解决方案。文献[4]提出了基于Shapley值的虚拟化资源分配策略,该理论的基础是合作博弈论,该方法高效地实现了虚拟化资源分配。针对资源分配中的利用率问题,文献[5]提出了基于分类挖掘的网格资源分配算法,通过分类减少资源重新分配次数,提高资源利用效率。Prodan等[6]提出了基于连续双向拍卖机制的资源调度方法,该方法同时兼顾了用户和服务提供商的双方利益;Martino[7]介绍了一种基于 遗传算法的网格资源调度算法,在花费一定能耗代价后, 能尽可能提高网格资源使用率和负载均衡能力。文献[8] 针对云计算的编程模型框架,提出了一种具有双适应度遗传算法,用于解决云计算模型中的资源分配最优化问题, 该算法不仅能得到总任务完成时间较短的调度结果,而且此调度结果任务平均完成时间也较短。文献[9]在充分考虑云计算环境动态异构性和大规模任务处理特性的基础上提出了一种改进遗传算法,并通过实验验证该算法能较好地适用于云计算环境中的大规模任务资源调度。以上文献提出的各种算法都可为本文提供借鉴意义,但是本文所提出问题情境、问题模型与上述研究均不所相同。
1仿真运行环境动态构建中遗传算法应用
1.1问题提出
本文研究仿真运行环境构建3层映射模型[2],如图1所示。构建仿真运行环境,分步将仿真模型动态部署到虚拟机,将虚拟机部署 到物理机,并分别实 现N:1映射关系。由于虚拟机与物理机两者之间的映射过程(第二步) 与仿真模型和虚拟机两者之间的映射过程(第一步)基本相同,只是获取虚拟机与物理机最优映射约束条件略有不同,因此本文对第二步不作讨论,只探讨仿真模型与虚拟机之间的映射最优化问题。
针对仿真模型与虚拟机之间最优化映射问题,关键是如何将与仿真任务有关的仿真模型映射到不等量虚拟机中,以保证提供的运行环境能满足仿真模型的解算和通讯需求,并且使仿真任务执行效率达到最优。
1.2问题数学模型及形式化定义
为方便研究,本文将仿真模型性能需求和虚拟机提供性能配置 折算为计 算性能和 通信性能[1],并分别用Wworkload和Wcom表示。计算性能由节点计算能力和内存大小决定,而通信性能 受限于网 络带宽和 网络延迟。如式 (1)所示:
其中,λ1和λ2为折算因子,Wcpu表示节点计算能力, Wmemsize表示节点内存大小。
其中,μ1和μ2为折算因子,Wwidth表示节点网络带宽,Wlag表示节点网络延迟。
仿真模型拓扑结构可以描述为四元组,S = {Ws,Rs, Cs,Ns}。其中,Ws表示仿真模型的集合,Rs表示仿真模型间通信的集合,Cs= {Csi|si∈Ws}表示仿真模型计算性能需求集合,NS= {nsp,q|sp,sq∈WS}表示仿真模型间通信性能需求集合。
虚拟机镜像的 拓扑结构 可以描述 为四元组T = {WT,RT,CT,NT},其中,表示虚拟机镜像的集合,WT表示虚拟机镜像间的通信集合,CT= {cti|ti∈WT}表示虚拟机镜像能够提供的计算性能集合,NT= {ntp,q|tp,tq∈ WT}表示虚拟机镜像间的通信性能集合。
设t=d(s)表示仿真模型s向虚拟机镜像映射,则仿真模型到虚拟机镜像映射关系可描述为四元组F= {WF, RF,CF,NF},其中WF表示仿真模型部署到虚拟机镜像后虚拟机镜像的集合,RF表示仿真模型部署到虚拟机镜像后虚拟机镜像间通信的集合,CF= {cfi|fi∈WF}表示虚拟机镜像ti上部署的仿真模型计算的需 求总和集 合,即表示虚拟机镜像tp上所部署仿真模型和虚拟机镜像tq上所部署仿真模型间通信需求总和集合,即
令
和
式(3)、式(4)分别表示仿真模型向虚拟机镜像拓扑结构映射计算性能比率和通信性能比率。设δ为映射过程d的性能指标函数,则δ(d)=max(coi,nop,q)表示映射过程d性能指标由所有计算性能比率和通信性能比率中的最大值决定,性能指标值越小,映射结果越优。设γ 为映射过程d整体通信量,由于同一个虚拟机中仿真模型间数据交互速度相对于不同虚拟机间数据交互速度可忽略不计, 因此,映射过程应尽可能将通信量大模型部署在同一个虚拟机镜像中,即使γ(d)=∑nfp,q值最小。
根据以上分析,假设仿真模型向虚拟机镜像最优映射为d*,那么该映射应能使得δ(d)和γ(d)取值最小。即目标函数为:
根据仿真模型与虚拟机数量的大小关系又有不同映射:
(1)若仿真模型数量小于或等于虚拟机数量,则在给虚拟机分配仿真模型时,将一个虚拟机上所有资源都占满再去分配其它虚拟机,直到将所有满足其计算需求和通信需求的仿真任务分配完毕,这样得到的映射关系使多个虚拟机上是没有仿真 模型,通过关闭 没有仿真 任务的虚 拟机,从而达到节约能耗的目的。该分配方式简单易操作, 本文不再赘述。
(2)若仿真模型数量大于虚拟机数量,则可以采用本节所介绍的映射模型,根据该方法得到的仿真模型到虚拟机间的映射,使得每台虚拟机资源最大使用率最小,进而使整个系统具有更大的灵活性。下面介绍遗传算法以实现本节中所提出的映射模型。
2改进遗传算法求解最优映射
遗传算法(Genetic Algorithm,GA)是美国Michigan大学J.H.Holland教授于1975年受Darwin进化论思想的启发而提出。其核心思想是生物进化过程从简单到复杂、从低级到高级,这本身就是稳健适应自然、适者生存的优化过程。相较于传统穷举法、微分法等优化算法,遗传算法不仅具有自组织、自适应、自学习的特性,而且具有高鲁棒性和广泛适用性,能突破问题性质限制,有效处理传统优化算法难以解决的复杂问题。遗传算法的主要优势在于是一种全局优化算法。搜索空间是问题解的结合,因而其搜索覆盖面更大,范围更广,并能进行多点并行搜索, 使得遗传算法能同时对多个解进行处理、评估,搜索广度和随机性更优,能避免陷入局部某个单峰最优解,同时有利于较快收敛到全局最优解。
2.1染色体编码方式
遗传算法中的染色体编码有很多种,如采用对任务执行状态的直接编码和间接编码。本文采用二进制染色体编码方式:M个仿真模型和N个虚拟机,M个仿真模型对应M个表示单元,而每个表示单元由若干个二进制位表示;每个表示单元的二进制位数k由虚拟机数量N决定,即2k-1< N ≤2k。因此,第一个表示单元的大小a表示第一个仿真模型映射到a号虚拟机上,第i个表示单元的大小,b表示第i个仿真模型映射到b号虚拟机上。最后,可以得出整个染色体长度是M*k个二进制位。
2.2初始种群生成
由上节可知,本文染色体表示仿真模型到虚拟机的映射。每一个染色体是一种仿真模型与虚拟机的映射方式, 且每一个染色体表示一个种群中的个体。本文初始种群为随机生成,初始种群数量设为Num 。算法是在这Num个种群中进行选择、交叉、变异,从而生成种群下一代。
2.3适应度函数
遗传算法是通过适应度函数值进行下一代的选择,从而寻找问题最优解。因此,适应度函数选取相当重要,关系到算法收敛速度与所得解的优劣。根据问题模型,要想达到仿真模型与虚拟机之间的最优映射,则必须满足目标函数,遗传算法适应度函数:
其中,二维数组v_cpu[x][j]表示x号染色体中j号虚拟机计算资源的使用率;三维数组v_com[x][j][k]表示x号染色体上虚拟机j和虚拟机k上已经部署的仿真模型之间通信量之和占虚拟机j与虚拟机k通信总量的比例。适应度函数值越小,映射性能越优,越容易被选择。
2.4选择、交叉、变异操作
2.4.1选择
在遗传算法中需对种群中的个体按照一定比例进行选择,该比例由适应度函数值决定,选择的目的是将拥有更好基因的个体直接遗传到下一代或将通过配对交叉产生的新个体遗传到下一代。本文使用轮盘赌选择方式将优秀个体挑选出来,通过适应度值计算出每个个体的选择概率:
其中,f(i)表示第i个染色体的适应度值,ps(i)即为i号染色体被选择的概率。
2.4.2交叉
交叉是遗传算法中最主要的搜索算子,其模仿自然界有性繁殖基因重组过程,将原有优良基因遗传给下一代个体,并生成包含更优良基因结构的新个体。交叉是产生后代并区别于父代的主要方式,其以较大概率选择两个个体进行基因位交换,交换后子代既保留了父代大部分基因, 也具有自己新的基因 特色,整个种群 基因会发 生相应改 变,从而保证种群向最优化方向发展。
2.4.3变异
所谓变异,是指将基因座上特定值进行改变。当遗传算法通过交叉算子已经接近最优解时,利用变异可以加速种群向最优解收敛。变异算子pm通常在0.000 1~0.1间取值,适当取值可保持种群多样性,同时防止未成熟收敛现象。本文所述遗传算法变异操作是对种群中的每个个体以pm的变异概率检查其是否发生变异,对进行变异的个体随机选择变异位并改变变异位的值。
2.5算法终止条件
本文采用的终止条件包括进化的代数G和阈值r ,一旦算法执行的进 化代数达 到G次或在下 一代所得 到的 δ(d*)与上一代计算得到的δ(d*)的差值小于r时,算法均终止。此时得到的结果是最优解或趋近于最优解。最优解种群中 对应的max(v_cpu[x][j],v_com[x][j][k]) 为最小的染色体,即为最优映射。
2.6模拟退火算法引入
模拟退火算法思想最先由Metropolis等于1953年提出,并在1983年被Kirkpatrick等成功引 入组合优 化领域。模拟退火算法可以看作一个物理模拟过程:从某个较高初始温度出发,先将固体加热至高温状态,此时固体分子间不断发生碰撞,呈无序状态,具有较高的内能;然后让高温固体慢慢冷却,固体分子将随着热运动的逐渐减弱而恢复到稳定、有序状态。在这个过程中,固体内部粒子在每个温度 下都能达 到平衡态,最终在常 温时达到 基态[10]。模拟退火算法采用Metropolis接受准则能避免过早达到局部最优范围,从而保证所求解的质量。该接受准则是指当固体处于较高温度状态时,接受新状态可能性较大,而当固体处于较低温度状态时,接受新状态可能性随之降低。最终,当温度趋于0时,任何使内能小于0的新状态都不能被接受。
经典遗传算法的早熟现象是指算法过早陷入局部最优,很难跳出局部走向全局最优。已有研究表明,由于群体规模限制,当该种群进化若干代后,具有较高平均适应度的指数级增长模式将在种群中占有绝对优势,也就是在自然界优胜劣汰中占据统治地位。如果不加以调整控制, 算法中的选择、交叉、变异操作将逐渐因为种群高度一致性而失去作用,整个种群的模式种类将越来越单一,最终导致算法陷入局部最优解[11]。将模拟退火算法引入遗传算法中,既能避免遗传算法存在的“早熟”问题,大大降低遗传算法陷入局部最优解的可能性,又能增强算法全局收敛特性,提高算法收敛速度。
因此,首先采用遗传算法框架进行最优化问题求解, 再引入模拟退火算法优化遗传算法中选择下一代种群的操作,根据Metropolis接受准则以一定概率接受坏解,从而在进化过程中保持种群多样性,最终得到最优解。
2.6.1Metropolis接受准则
设当前状态下温度值为T,根据粒子当前所处的相对位置,设固体初始状态为i,对应内能为Ei;随后随机选取其中的某个粒子,按随机产 生的偏移 向量使粒 子发生偏 移,设偏移后的状态为j,此时内能为Ej。若Ej<Ei,则接受j为当前状态,否则采用 如下方法 判断是否 接受新状 态:设,其中K为Boltzmann常数,T为温度。设β∈[0,1],若α>β,则接受该新状态,否则拒绝改变状态。通过重复上述过程,系统能量将逐渐降低,最终达到平衡状态。
2.6.2模拟退火算法参数
(1)温度控制初始值t0。该值选取不宜过大或过小。 过大的选择将导致退火算法收敛缓慢,失去可操作性;过小的选择会导致退火算法陷入局部搜索。
(2)温度控制终值tf。该值决定模拟退火算法终止条件,即温度达到某个充分小的值表明算法收敛到某个近似解。本文采取判断算法求解的近似性决定是否终止,若迭代若干次后得到的解没有变化,说明算法解的质量无法进一步提高,从而宣告算法终止。
(3)温度衰减函数f(tk)。本文取一种常用的衰减函数f(tk):tk+1=μtk,u∈ [0.5,1)。
2.6.3改进遗传算法流程
本文提出的SAGA算法(Simulated Annealing Genetic Algorithm)分两个阶段:在遗传操作阶段,利用选择、交叉和变异过程对初始种群Gi进行遗传操作,产生进化后的种群G珚i;在模拟退火操作阶段,将种群G珚i作为输入,釆用模拟退火操作,通过Metropolis准则对G珚i中的个体进行筛选,产生新一代种群Gi+1。具体操作步骤如下:
Step 1:初始化种群。根据仿真模型与虚拟机的数量采用随机方式生成初始种群,初始种群规模记作Mg 。设定进化迭代参数i为0;
Step 2:计算目标函数与自适应函数。首先计算当前种群适应度函数f(i)和最优映射值δ(d*);
Step 3:终止条件判断。当进化代数达到预定最大进化代数或在下一代所得到的δ(d*)与上一代计算得到的 δ(d*)差值小于r时算法终止,输出搜索结果,否则继续执行;
Step 4:选择操作。采用轮盘赌法对种群进行选择操作,根据式(7)得到的ps概率来选择适应性较强的个体, 形成新群体,进行下一步交叉操作;
Step 5:交叉操作。釆用交叉 方法,从经过选 择操作产生的群体中随机选择2个个体进行交叉操作,产生2个新个体;
Step 6:变异操作。釆用变异操作方法对被选中个体进行变异操作,将符合要求的新个体放入种群;
Step 7:在温度ti下,计算遗传操作后种群中每个个体的适应度值;
Step 8:根据适应度函数和Metropolis接受准则,判断是否接受当前遗传算法产生的新个体;
Step 9:更新进化迭代计数i=i+l,转到Step 2。
3实验测试
CloudSim是一款云计算仿真工具,是用于实现对云计算基础设施和应用服务进行模拟的开源框架。本文使用CloudSim中的DataCenterBroker方法实现算法调度策略。
3.1实验条件设定
算法参数设置如表1所示。本实验中仿真模型数量取值为1k、2k、3k、4k、5k,逐渐增大。虚拟机数 量设为500。仿真模型计算资源需求量取值范围为 [1,20],数值越大表示对计算资源的需求越大。虚拟机可以提供的计算资源取值范围为 [100,300]。设仿真模型间所 需通信性能取值范围为 [1,20],虚拟机间可用通信性能取值范围为 [100,300]。限定任何一个虚拟机上面部署 的仿真模型计算资源需求量之和都不能超过此虚拟机提供的计 算资源。
3.2与经典算法对比
在相同实验条件下,将本文提 出的SAGA算法与经 典GA算法(遗传算法)、RA算法(随机分配算法)分别进行比较。实验结果如图2所示。
由图2可知,随着仿真模型数量的增加,染色体长度越长,染色体就越复杂,相应的交叉、突变也越复杂,因此要得到最优解或接近最优解的部署,算法需要的运算时间越多。当仅有少量仿真模型时,传统的GA算法和SAGA算法都能够迅速收敛,执行时间差别不大,而RA算法由于随机性较大,花费时间稍多。当仿真模型数量较多时, 传统GA算法收敛代数急剧增加,搜索效率大大降低,而随着任务量的增大,SAGA算法的优 势越来越 明显,SAGA算法能保持群体多样性,推动群体稳定进化,从而所需时间随着仿真模型数量增加而变化更加平滑。传统RA算法随着搜索空间越来越大,性能下降很明显,可见RA并不适用于云环境下大规模仿真数据处理。
图3显示不同数量仿真模型算法分派资源最大占用率,该值越小则算法性能越优。总体而言,随着仿真模型增多,3种算法计算资源最大占用率都在增大,RA算法由于采取完全随机分配策略,在仿真模型不断增多后表现最差,最后一组实验资源利用率已近90%,负载提升空间不大。GA算法和SAGA算法都表现出能根据虚拟机运算能力合理分配资源特性,算法倾向于使计算能力强的虚拟机分配到更多任务。虽然传统GA算法在问题规模较小时性能较好,但容易陷入局部最优解,反而导致性能下降。 本文提出SAGA算法能有效避免算法早熟,随着资源利 用率提升,能够提供更好负载均衡效果。
4结语
面向统计编码的联合比特分配算法 篇5
实现满意的统计编码系统需要编码器的有效控制,对每个节目复杂度的评估是实现有效控制的前提。传统的评估方法分为前向策略和反馈策略,基于反馈策略方法是在编码一帧或多帧之后进行,通过统计已编码帧的特性预测未来帧的信息,对复杂度评估比较粗略,尤其出现场景切换时,预测信息具有很大误差,不能对图像变化和场景切换做出快速、准确的响应[2]。
传统基于前向策略方法是在图像编码前,通过专用的图像复杂度评估模块提取复杂度信息,虽然能对图像复杂度变化和场景切换做出迅速响应,但增加了系统成本[3]。还有算法通过双行程编码实现统计编码,即一个编码器用来预算节目比特,另一个编码器(输入相应延后)用来对码流进行实际编码,该方法的缺陷是增加了编码的复杂度。
基于现有算法的缺陷,本文提出一种统计编码算法,将原始帧作为参考帧,通过并行整像素运动估计计算各编码帧的绝对差值和(SAD)来实现对图像复杂度的评估。由于是基于并行计算可以快速准确地统计未来多帧的复杂度信息,能够对图像变化、场景切换做出迅速响应,也满足了图像的连续性需求。并行整像素运动估计模块还完成了编码器运动估计的大部分工作,没有增加系统成本,并且由于运动估计是并行计算,提高了编码效率。实验结果表明本文提出的统计编码算法提高了节目的整体质量,取得很好的统计编码性能。
1 统计编码框架
传统统计编码可以分为两类,一是以文献[3-4]为代表的基于反馈预测的统计编码算法,如图1中标号①所示,其原理是通过对前一编码帧的内容分析统计出复杂度信息,通过预测计算出当前帧的复杂度信息,作为比特分配的控制参数。文献[3-4]分别提出了不同的预测模型,其中经典的预测模型为线性预测,如式(1)所示
式中:α和β为预测系数,Ci为第i帧的复杂度。由式(1)可知当前编码帧的预测值和前一已编码帧的复杂度有很大的相关性。当出现场景切换时,由于复杂度可能相差很大,将出现很大的预测误差。为解决此问题,以文献[5]为代表提出了前向统计策略,在编码前加入复杂度评估模块提前统计出当前帧的复杂度信息,此方法虽然避免了预测误差,但复杂度评估模块没有完成其他编码工作,增加了系统成本,原理如图1标号②所示。根据上面分析可知,传统的统计编码算法可能存在以下两个缺陷:1)存在预测误差;2)增加系统成本。
由于传统的编码框架是将重建帧作为参考帧进行运动估计,无法将运动估计模块独立出来。如图2所示,本文提出将原始帧作为参考帧,将整像素运动估计模块独立出来,计算出已缓存各帧的SAD,并将其作为表征复杂度的参数,由于SAD是实际计算得出,不存在预测误差。同时整像素运动估计模块还计算出整像素运动矢量MV',在编码模块将MV'作为搜索起始点进行亚像素运动估计获得最终运动矢量MV,减少了编码模块的计算负荷。因此,整像素运动估计模块没有增加系统成本。此外,统计编码大多应用在实时广播系统中,对实时性要求很高,因此在整像素运动估计模块中并行计算SAD,能够快速准确地统计未来多帧的复杂度进行联合比特分配。
2 统计编码算法
2.1 计算图像复杂度
由于统计编码实质是根据不同的图像特性分配大小合适的目标比特,提高信道利用率,因此图像复杂度定义为在保证图像质量的前提下,能够反映编码一帧图像所需比特数多少差异的量。
在整像素并行运动估计模块,将原始帧缓冲N帧,根据帧类型确定编码帧的参考帧[6],参考帧的选取和AVS编码标准相似,其中I帧为帧内编码;P帧参考编码顺序的前一I帧或前一P帧;B帧参考前后两帧,假设原始序列顺序为IBBPBBP,参考帧选取如图3所示。
图3中箭头指向即为该帧的参考帧,参考帧确定后将原始帧作为参考帧,对已缓冲的帧进行整像素运动估计计算各编码帧的SAD,如式(2)所示。
式中:A代表像素区域,当前帧为I帧时,S为当前块的像素值,S'为预测块的像素值;当前帧为P帧时,S为当前帧的像素值,S'为参考帧预测图像的像素值。当前帧为B帧时,分别计算当前帧和两个参考帧的SAD(计算过程和P帧相同),最终该帧SAD取两个SAD的均值。
由式(2)可知SAD是实际计算出的图像绝对差值和,能准确反映图像的纹理信息,而编码所需比特大小差异主要由纹理特性决定[4]。此外,在视频编码标准H.264、AVS中都将SAD/MN(即MAD)作为图像复杂度参数进行码率控制,其中MN为宏块大小,因此SAD能够作为表征图像复杂度的参数。由于运动估计基于原始帧,本文采取并行运动估计,利用多线程根据式(2)计算各帧的SAD,能够快速准确地为统计编码提供未来多帧的复杂度信息。
2.2 比特分配控制参数
为了满足图像的连续性,同时对图像变化做出快速准确的响应,本文统计当前帧和未来M-1帧的复杂度信息作为比特分配控制参数,比特分配控制参数complex计算如
其中:j为当前编码帧;complex(t,p)为t时刻第p个节目的比特分配参数;M为大于或等于1的整数,是事先设定的值;SAD(t,p,i)为t时刻第p个节目第i帧的SAD。
2.3 各节目的比特分配
由于各路节目的优先级可能不同,为了保证节目所要求的图像质量,为每个节目设置最大码率m_maxrate和最小码率m_minrate。各节目比特分配步骤如下所示:
1)首先对每一路输入按照步骤2.2计算的比特分配参数进行比特初始分配,即
式中:m_allocarate(t,p)为t时刻第p个节目流分配的比特;N为复用的节目总数(p<N);total_rate为所复用节目总比特数。Complexity为当前统计的总复杂度。
2)遍历各个节目的初始比特分配,如果m_allocarate(t,p)<m_minrate,该节目分配的比特更新为m_minrate。总复杂度Complexity更新为Complexity-complex(t,p),复用节目总比特total_rate更新为total_rate-m_minrate,该节目比特分配完成,遍历结束进入步骤3)。
3)根据式(4)对比特未分配完成的节目进行再分配。遍历这些节目,如果m_allocarate(t,p)大于m_max,该节目分配的比特更新为m_maxrate,Complexity更新为Complexity-complex(t,p),total_rate更新为total_ratem_maxrate,该节目比特分配完成,遍历结束进入步骤4。
4)根据式(4)为比特未分配完成的节目进行再分配,为最终分配比特,比特分配结束。
2.4 算法流程
1)整像素并行运动估计模块为统计复用模块统计图像复杂度。
2)统计复用模块根据2.2小节计算当前时刻各节目的比特分配控制参数。
3)统计复用模块根据2.3小节为节目分配比特,并将分配的比特传递给编码模块。
4)编码模块通过文献[7]的基于并行编码的码率控制调节量化参数,从而使得节目比特在所分配的恒定的范围内。
5)经固定时间更新各节目的比特分配,重复步骤2)~4)。
3 实验结果与分析
3.1 测试环境
为了验证所提出的统计复用算法性能,视频编码采用AVS+,视频大小720×576,CBR模式下视频码率设置为2 000 kbit/s,码率波动范围设置为1 000~4 000kbit/s,GOP为50,复用类型为TS,输出类型MUX,输出码率9 500 kbit/s,采用如表1所示的4组测试序列,本方法已应用于某编码器,经权威部门分别对VBR和CBR情况下的码率以及图像质量(PQR)进行检测,其中VBR为采取本文统计编码算法的情况。
3.2 视频码率检测
用码流分析仪对AVS+编码器输出码流进行实时统计分析,循环三遍的实时码率统计如图4~5所示。
通过分析图4和图5可以得出,在采用CBR模式情况下,无论节目复杂度高低,各节目的码率都在2 000 kbit/s附近波动,对于高复杂度视频码率采用2 000 kbit/s影响图像质量,对于低复杂度视频码率采用2 000 kbit/s造成比特浪费。本文提出的统计复用算法的总码率和CBR条件下相近,在7 854.6~8 736.5 kbit/s之间,但使用本文算法,通道1(低复杂度节目)的实时码率在1 400 kbit/s上下波动,通道2、通道3(中等复杂度节目)的实时码率在2 000 kbit/s上下波动,通道4(高复杂度节目)的实时码率分别在2 950 kbit/s上下波动,很好地根据图像复杂度进行波动变化,使复杂度高的视频节目分配较多比特,达到很好的复用性能。
3.3 图像质量PQR对比
对图像质量的测试采用PQA600A,它采用基于人类视觉系统的概念,提供一整套可重复的、并与主观人眼视觉评估十分接近的客观图像质量测量。利用图像质量分析仪对编解码后的图像进行采集和分析,得到逐帧的PQR值(PQR值越小代表图像质量越好)如图6~7所示曲线图。
在序号1~500场景下,通道3和通道1节目复杂度相差较大。VBR模式下,通道1相对CBR稍下降(仍具有很好的图像质量),但通道3图像质量提升明显。
在序号500~1 000场景下,4个通道的复杂度信息差距较大,在CBR模式下通道1、通道2图像质量较好,通道3、通道4图像质量较差。在VBR模式下,通道1、2相对CBR模式下稍有下降,通道3、4的图像质量得到很大提升。
在序号1 000~1 500情境下,4个通道复杂度差距减小,在CBR和VBR模式下都取得了很好的图像质量。
在序号1 500~2 000情境下,通道3复杂度增大,在CBR模式下图像质量较差。VBR模式下,通道1、2、4图像质量相对CBR稍下降(仍具有很好的图像质量),但通道3的图像质量得到极大提升。
如表2所示,各通道图像质量:通道1、通道2在CBR模式下PQR均值分别为3.30,6.60,已经达到了很好的图像编码质量;在VBR模式下PQR值分别增大了0.80和0.10,图像质量相对有所下降,但仍保持很高的图像质量。通道3、通道4在CBR模式下PQR值分别为14.8,10.0,图像编码质量较差,在VBR模式下PQR值分别降低了2.60和1.10,图像质量得到了极大的提升。
总体图像质量:CBR模式下,4个通道总的PQR均值为8.60,均方差为4.30;VBR模式PQR均值为8.00,均方差为2.97;总体图像质量相对于CBR模式,PQR下降0.60,均方差下降1.33。
通过对图6、图7以及表2的分析可得,相对于CBR模式,采用本文的统计编码算法使质量好的节目稍有下降,但仍保持很好的图像质量,质量差的节目质量得到显著提高,缩减了节目间的质量差距,提高了整体图像质量,达到很好的统计编码效果。
4 结束语
本文首先分析当前统计复用算法的缺陷,提出了一种新的统计编码算法。测试了CBR模式下和本文提出的统计算法的视频码率以及PQR值,通过实验数据分析来说明本文提出的算法提高了节目的整体质量,取得了很好的统计编码性能。
摘要：在统计编码系统中,需根据图像复杂度对各路节目进行联合比特分配,比特分配的准确性直接影响了图像质量。因此对图像复杂度的准确评估是统计编码的难点。鉴于传统的基于预测的算法对复杂度评估存在预测误差,提出了将原始帧作为参考帧,通过并行整像素运动估计计算各编码帧的SAD作为统计所需的复杂度信息,提高了图像复杂度评估的准确性,进而提高统计编码性能。通过测试CBR模式下和提出的统计算法下的视频码率以及图像质量来说明所提出算法的可行性。
关键词：统计编码,联合比特分配,复杂度评估
参考文献
[1]董焱鑫,李桂苓,模块化联合码率控制技术[J].电子技术应用,2000,8(19):48-50.
[2]HE Z,WU D O.Linear rate control and optimum statistical multiplexing for H.264 video broadcast[J].IEEE transactions on multimedia,2008,10(7):1237-1249.
[3]BRCZKY L,NGAI A Y,WESTERMANN E F.Statistical multiplexing using MPEG-2 video encoders[J].Ibm journal of research&development,1999,43(4):511-520.
[4]YANG J,FANG X,XIONG H.A joint rate control scheme for H.264 encoding of multiple video sequences[J].IEEEtransactions on consumer electron,2005,51(2):617-623.
[5]BOROCZKY L,NGAI A Y.Joint rate control with look-ahead for multi-program video coding[J].IEEE transactions on circuits and systems for video technology,2000,10(7):1159-1163.
[6]JIANG X C,LI G P.A novel parallel video coding frame work for AVS+real time encoder[C]//Proc.Pacific-Rim Conference on Multimedia.Nanjing:Springer International Publishing,2013:170-179.
EPON动态带宽分配算法的研究 篇6
关键词：EPON,DBA,轮询
0、引言
随着光纤通信成为现代通信的主流技术，在向着全光网络的发展过程中，EPON结合以太网和无源光网络技术，具有协议简单、成本低、带宽高、易于兼容等优点，成为解决"最后一公里问题"[1]的最佳解决方案之一。但与APON相比，EPON存在一个天然的缺陷，即不能很好的支持QoS (Quality of service) ，不能很好的满足三网合一的需求。要成为宽带接入的主流技术并大举进入市场，必须既能稳定地支持传统的电话业务、数据业务，又能高效地保证新兴实时性业务如网络电视，视频点播 (VOD, video on demand) 等的质量，因此进一步对EPON的带宽分配算法的研究有着非常重要的意义。
1、EPON的基本原理
EPON是采用PON的拓扑结构实现以太网接入的网络，由三个部分组成：光线路终端（OLT）、光分配网络 (ODN) 和光网络单元 (ONU/ONT) [2][3]。如图1所示，OLT处于局端，可以是一个交换机或路由器，也可以是一个提供面向无源光纤网络接口的多业务平台，向上介入上一层网络，向下为ONU或用户提供带宽分配、网络安全和管理等功能。ODN是一个光分路器，分光能力在1:16到1:128之间。ONU处于用户一侧，根据采用的配置方案（如FTTH、FTTB等）不同，具体的位置也不同，全光网络中ONU可置于用户家中，ONU可通过层叠为多个终端用户提供共享高带宽的服务。
EPON网络中，采用可变长的数据包，最高可达1518字节，上行方向采用1310nm波长，下行方向采用1550nm，波长传输速率为1.25Gbit/s。如图2 (a) 所示，由OLT到ONU下行采用广播的方式，通过ODN将数据包发送给所有的ONU，由于每个ONU在注册时都被分配了唯一的ID，通过读取数据包中的ID，只有与本ONU的ID符合的才会被接收，其他的数据包将被丢弃。如图2 (b) 所示，上行采用TDMA技术，实现多点到点的接入，帧与帧之间需要一个时间空隙，即保护时间，OLT可以在这段时间内对接收器进行调整电平的增益，保护带宽最大为2us。因为多路信号要共享一根光纤，有可能会出现碰撞现象。EPON利用多点控制协议（MPCP）进行OLT和ONU之间的通信，由OLT根据网络情况，统一为ONU分配带宽（使用时隙），基于网络严格同步的情况下，既可以避免碰撞（非初始注册过程）现象，又可以利用一定的带宽分配算法，实现高效的带宽利用率。一个完善的DBA方案应包括轮询机制和带宽分配算法两部分，下面从这两个方面入手来对EPON系统的带宽、包时延、丢包率、Qos等性能参数进行研究。
2、轮询机制
EPON的MPCP提供的REPROT和DATE帧为OLT和ONU之间的信息互动提供了支持，这种Request-Grant问答机制，为带宽分配提供了实现手段。轮询的顺序也有多种选择，可以按根据注册先后顺序确定的固定顺序轮询、按负载的轻重重的在前轻的在后或者反过来等等，结合各自算法的特点来进行选择。典型的轮询是基于周期的，在一个周期内，OLT对ONU逐个询问需求情况，并根据请求授权带宽。因此从轮询周期的角度又可以分为：固定周期轮询、可变周期轮询 (自适应周期轮询) }]和周期一定受限的轮询[4]。
轮询周期固定，一定固定时间内的下行授权帧数就固定，不会随着上行网络负载的增大下行授权控制的插销。但是当系统带宽满足了所有ONU的请求后还有残余时，却因为周期的固定性而无法顺延至下一轮继续使用，降低了带宽利用率。
典型的可变周期轮询是IPACT算法，它根据ONU上报的队列长度进行带宽授权，从而在一周轮询下来得到的轮询周期是不固定的。这种轮询周期的带宽利用率比较高，上行信道利用率可以逼近于1，但它的不足在于：轻负载时，轮询周期很小，授权帧的发送频率极高，会消耗相当一部分的下行信道带宽；一部分业务量大的用户总能得到足够的带宽，从而使周期变长，使得业务量少的用户的时延加大，违反了公平性的原则。
周期可变的轮询机制，为周期设定了一个范围，一定程度上解决以上的问题。同时，此时的轮询周期的大小可以一定程度上反映网络负载的情况。目前，考虑到公平性问题，防止个别高负载的用户垄断着信道，OLT会以一定的标准来限制对每一个ONU的开窗大小进行限制，称为最大带宽限制问题，在重负载的情况下，它就可以决定最大的轮询周期，但是如果开窗过大，就会导致所有的帧的延时更长，如果太小，就会把带宽浪费在保护带宽上。目前对于轮询周期的下限还讨论不多。
除了上面介绍的轮询机制以外，带宽分配机制将对DiffServ[5]的处理反映在了轮询机制上。OLT对同一优先级的用户进行集中授权，这样做的好处就是保证了高优先级业务的带宽，提高服务质量。为了算法的需要，则是将数据与控制帧分离，此时ONU上报的队列长度更加接近上传时刻的队列长度值，可以减小时延，同样它也需要增加保带宽。
总之，轮询机制是时隙分配机制的一个组成部分，根据不同的算法和追求目标的不同，可以适当选择自己的轮询分配机制，同时也可以通过轮询机制来弥补算法中的不足。
3、带宽分配算法
带宽的分配主要分为静态和动态两种:静态带宽分配 (SBA，又叫固定时隙分配) 按照各ONU预定的带宽进行初始配置，运行期间不管实际的网络状况如何该值不变。SBA简单，容易实现，但是没有实现带宽的统计复用，带宽的利用率低。动态带宽分配 (.DBA) 是指OLT根据即时的网络业务情况对每一个ONU逐个分配带宽，一个周期更新一次，很明显，DBA的带宽利用率比SBA要高，上行带宽毕竟是有限的，为了让所有的终端用户都能尽可能的满意，DBA更能满足要求。下面就来分析几个主要的DBA算法。:
3.1 带宽受限分配算法（LBA)
LBA通过REPORT/GATE来跟踪业务量，每个ONU的可分配的最大带宽根据用户等级、业务类别等来确定。如果请求的带宽长度小于这个值时，就分配给它请求的带宽，否则就按这个值来授权。LBA通过报告队列长度的方式来跟踪业负载，由于业务流量是动态的，所以它的分配时隙大小也是变化的，因为每个轮询分配的时隙也是不同的，所以最终导致它的轮询周期也是变化的。LBA的保守性表现在通过对每个ONU的授权的限制来抑制了带宽的恶性竞争，不会出现业务量大的用户独霸着带宽，业务量小的用户得不到带宽的现象。LBA也是目前使用最广泛，性能最好的DBA算法之一，它的带宽利用率比较高。
3.2 基于信用的带宽分配算法 (CBA)
在REPORT/GATE机制下，每个ONU发送完REPORT帧后都经历了一段等待时间后才能继续发送缓冲区内的数据。ONU在t1时刻上报队列长度，在t3时刻开始上传数据，在t1到t3这段等待时间内，仍然有可能有新数据进入缓冲区内。如果在t1时刻上报队列长度时，对下面等待时间内可能新到的业务量进行估算，那么新到的数据帧就不需要多等一个周期再发送。CBA就是把这部分等待周期内可能新进入的数据帧也考虑进去，在原来上报的队列长度的基础上再加上了一个信用C，这里C可以是常数，也可以是线性表达式。线性信用是基于网络业务的可预测性，因为一般长突发业务会持续一段时间，前一周期的信息对后一周期的等待周期的新增业务量具有价值，可以进行一定程度的预测。
这种带估算的带宽分配方法的好处在于可以减小部分帧时延，但是估算要根据不同业务的特点来设计，而且也不是任何估算都是有益的，因为以太帧是不定长的，如果估算分配的带宽不足以满足实际的帧通过，很可能带来新的带宽浪费。
3.3 弹性带宽分配算法 (EBA)
EBA是在LBA的基础上的一个变通。LBA中每一个ONU都有一个最大开窗，每个ONU的授权都不可以超过这个值，E-BA中取一个最大总授权带宽值，所有轻负载ONU使用完后残余的那部分带宽，在一个周期内进行再此分配。很明显这种分配方式往往是收集完所有的ONU的信息之配处理的，它必须与相应的轮询机制结合使用，同时这种算法容易实现公平性分配，是使用比较广泛的算法。
4、结论
EPON作为众多宽带接入的最佳方案之一，有着协议简单成熟、标准化程度高、建设维护成本低廉的巨大优势，要更好的满足用户的Qos，对EPON的带宽分配算法进行研究有着非常重要的意义。本文从EPON的工作原理入手，深入讨论了各种带宽分配算法的优势和劣势，不同的算法必须采用相应的轮询机制，对性能参数的制约也各有不同，因此必须进一步根据具体的网络用户的需求来设计制定带宽分配方案。
参考文献
[1]Kramer G, Pesavento G.Ethernet Passive Optical Network (EPON) :Building a Next-Generation Optical Access Network[J].IEEE Communica-tion Magazine, 2002, 40 (2) :66-73.
[2]孙学康张金菊.光纤通信原理.北京:人民邮电出版社, 2004
[3]原荣.宽带光接入网.北京.电子工业出版社.2003
[4]李莉莉符建.一种轮询周期受限的EPON双级动态带宽分配算法.光电工程.2006.33 (9) :110-114
新的分层系统信道分配算法浅析 篇7
关键词：分层系统,信道分配,阻塞率
在无线通信系统中, 信道是一种很稀有的资源, 为了满足大量的无线通信业务需求, 有限的信道资源需要合理的分配。现有文献对分层系统中的信道分配问题做了大量的工作。分层系统中的信道分配算法可分为固定信道分配 (FixedChannelAllocation, FCA) 和动态信道分配 (Dynamic Channel Allocation, DCA) 。FCA算法比较简单, 但是性能较差;带层间溢出的FCA算法的性能有所改进;而DCA算法比FCA算法有比较显著的性能优势。本文针对实际应用需求, 提出了一种新的动态信道分配算法。
1 信道分配算法
在单层蜂窝系统中, 基于紧凑模式的信道分配策略已经成为共识[4]。图1为7个小区的紧凑信道复用模式, 图中 (i, j) (1#i 7, 1#j 7) 表示一个两层的HCS结构 (为了表示的方便, 图中未画出微小区) , 宏小区可以表示为 (i, j, 0) , 微小区可以表示为 (i, j, k) (1#k 7) 。
两个宏小区 (i, j, 0) 和 (i, j, 0) , 可使用相同频率集合的条件为:
由此得到宏蜂窝 (i0, j0, 0) 的紧凑蜂窝为: (i, j0, 0) i1i0 (2)
两个微小区 (i, j, k) 和 (i, j, k) 可使用相同频率集合的条件为:
由此得到微蜂窝 (i0, j0, k0) 的紧凑蜂窝为: (i, j, k0) , i构i0或者j j0 (4)
1.1 CP-HDCA-BO算法
文献[4]提出了层间动态信道分配且带层间呼叫溢出的CP-HD-CA-BO算法, 其中还考虑了信道排序重组与层内紧凑模式分配信道的思想。该算法包括信道分配和信道释放两部分。
1.1.1 CP-HDCA-BO算法信道分配
CP-HDCA-BO算法首先将所有信道存放在信道池中, 并对信道进行编号。信道分配时, 微 (宏) 蜂窝从小到大 (从大到小) 申请信道。
慢速呼叫信道分配流程如所示, 慢速呼叫首先向所在微小区申请编号最小的空闲信道, 如果没有空闲信道, 则向信道池申请编号最小的信道, 并将此信道分配给此微蜂窝以及与此微蜂窝共道紧凑微蜂窝, 如果信道池中没有空闲信道, 则该慢速呼叫申请溢出到其所在的宏蜂窝, 如果宏蜂窝中有空闲信道, 则选择一个编号最大的信道分配给该呼叫, 如果宏蜂窝中没有空闲信道, 则该慢速呼叫被阻塞。
快速呼叫信道分配流程如图2所示, 快速呼叫首先向所在宏小区申请编号最大的空闲信道, 如果没有空闲信道, 则向信道池申请编号最大的信道, 并将此信道分配给此宏蜂窝以及与此宏蜂窝共道紧凑宏蜂窝, 如果信道池中没有空闲信道, 则该快速呼叫申请溢出到其所在的微蜂窝, 如果微蜂窝中有空闲信道, 则选择一个编号最小的信道分配给该呼叫, 如果微蜂窝中没有空闲信道, 则该快速呼叫被阻塞。
1.1.2 CP-HDCA-BO算法信道释放
当一个慢 (快) 速呼叫结束, 释放信道c1, 在该呼叫所在的微 (宏) 蜂窝中寻找被占用的编号最大 (小) 的信道c2, 若c2>c1 (c1>c2) , 将信道c2上的呼叫切换到信道c1;检测占有信道c2的紧凑共道蜂窝中信道c2的使用状态, 如果信道c2在这些蜂窝中都处于空闲状态, 则将信c2道归还到信道池。
仿真结果表明, CP-HDCA-BO算法能够获得较低的呼叫阻塞率。但是, CP-HDCA-BO平等地对待了新呼叫和切换呼叫。由于中断正在进行的呼叫比拒绝新到达的呼叫更不能让人接受, 所以, 在信道分配时, 切换呼叫应该有更高的优先级。本章针对CP-HDCA-BO算法的不足提出了一种新的考虑切换呼叫优先级的信道分配算法。
1.2 新的信道分配算法
本节针对CP-HDCA-BO算法的不足, 提出一种新的信道分配算法。新的信道分配算法在CP-HDCA-BO算法的基础上, 通过为切换呼叫预留信道的方法提高切换呼叫的优先级。新信道分配算法将系统中的信道分为两个部分:公共信道和切换预留信道。算法的步骤如图3所示, 当有一个呼叫到达时, 系统首先在公共信道集合中按照CP-HD-CA-BO算法为该呼叫分配信道, 如果能分配到信道, 则分配过程结束;如果该呼叫不能分配到公共信道, 且该呼叫为新呼叫, 则阻塞该呼叫;若该呼叫为切换呼叫, 则继续在切换预留信道集合中按照CP-HD-CA-BO算法为该呼叫分配信道, 如果能分配到信道, 则分配过程结束;否则, 阻塞该呼叫。
2 仿真结果
本节进行数值仿真, 并将结果与CP-HDCA-BO算法比较, 以验证本文所提信道分配算法的性能。仿真场景如表1所示。假设每个小区中快速呼叫和慢速呼叫的到达率相同。
仿真得到新呼叫阻塞率、切换呼叫阻塞率与呼叫到达率的关系曲线分别如图4和图5所示。
仿真结果表明, 与CP-HDCA-BO算法相比, 本文所提新的信道分配算法在牺牲一定的新呼叫阻塞率前提下, 能获得更低的切换呼叫阻塞率。
3 结论
本文研究了分层覆盖系统中的信道分配问题, 并提出了一种新的动态信道分配算法。该算法考虑了层间呼叫溢出、层内信道紧凑复用、提高切换呼叫优先级等因素。根据实际应用需求, 新的信道分配算法, 为切换呼叫预留信道, 有效地降低了切换呼叫阻塞率。
参考文献
[1]蒋体刚.多层蜂窝系统无线信道资源管理研究[D][博士论文].成都:西南交通大学, 2005.
[2]Chih-Lin I, Larry J.Greenstein, Richard D.Gitlin.A Microcell/Macrocell Cellular Architecture for Low-and High-Mobility WirelessUsers[J].IEEE jour-nal on selected areasin communications, Vol.11, No.6, 1993.
[3]X.Lagrange, P.Godlewski.Performance of a hierarchical cellular network with mobility-dependent hand-over strategies[J].IEEE Vehicular Technology Conf., vol.3, 1996.