动态资源分配算法

动态资源分配算法（精选11篇）

动态资源分配算法 第1篇

人工蜂群算法(artificial bee colony ABC) 自2005年土耳其学者Karaboga[1]提出以来, 得到了学术界的广泛关注。人工蜂群通过对蜂群内部分工机制及其觅食行为的模拟, 产生群体智能行为。与遗传算法(GA)、差分进化算法(differential evolution,DE) 和粒子群优化算法(particle swarm optimization,PSO) 相比较,ABC算法的求解质量相对较好, 具有操作简单、控制参数少、搜索精度较高和鲁棒性较强的特点[2], 对目标函数和约束几乎没有要求, 在搜索过程中基本不利用外部信息,仅以适应度函数作为进化的依据[3]等优点。ABC算法已经成功应用于人工神经网络训练、网络优化、机器人路径规划、滤波器设计、生产调度等多个领域。

ABC算法主要存在以下问题:1)ABC算法存在“早熟”的收敛性缺陷[4];2)ABC算法具有较好的探索能力, 但开发能力不足;3) 局部搜索能力较弱, 收敛速度相对较慢[5]。针对ABC算法的不足, 国内外的学者提出了较多的改进方法, 研究成果可归纳为算法参数调整、混合算法和设计新的学习策略3 个方面。Akey和Karaboga[6]系统研究了参数设置对ABC算法性能的影响, 在基本ABC算法的基础上增加了修改率(modification rate,MR) 的参数, 其用于控制搜索的扰动维数[7]方法。肖剑等[8]改进人工蜜蜂群全局搜索能力,引入Levy飞行策略, 对原始人工蜜蜂群算法进行改进。易正俊[9]等针对人工蜂群算法易陷入局部最优问题, 将蜂群算法中的跟随蜂数量翻倍, 用其一半采用轮盘赌选择机制更新, 增加的一半跟随蜂采用反向的轮盘赌选择机制, 用以维持种群的多样性。

本文为了提高算法的前期收敛速度和后期的探索能力, 主要做了两方面的改进工作:(1) 讨论了引领蜂数量对算法收敛速度和全局开采能力的影响, 在优化过程中动态调整引领蜂在种群中的比例。(2) 针对算法后期收敛速度慢, 易陷入局部最优的不足, 利用被抛弃蜜源信息和随机蜜源两种方式,产生优质潜在侦查蜂位置信息,有效提高搜索效率。

论文的结构如下: 在第二部分中对人工蜂群算法模型进行了描述, 第三部分论述了引领蜂和侦查蜂动态调整的策略, 提出动态种群分配人工蜂群算法(OS-ABC),第四部分进行了仿真验证, 并对结果进行了分析。

2 人工蜂群算法描述

ABC算法是模拟蜜蜂以协同的方式高效完成采集蜂蜜的工作过程而提出来的群体智能算法。蜂群中的蜜蜂根据分工可划分为引领蜂、跟随蜂和侦察蜂3 种。蜂群实现群体智能的模型包括蜜源、引领蜂、跟随蜂和侦察蜂共4 个组成要素, 以及引领蜂探索、招募跟随蜂和放弃蜜源并派出侦查蜂3 种基本的行为。蜂群通过引领蜂、跟随蜂和侦察蜂3 类不同角色的转换, 从而共同协作寻找高质量的蜜源[7]。

ABC算法中, 食物源的位置代表空间中的一个潜在解, 每个食物源的蜂蜜量代表着潜在解的质量, 即适应度值(Fit), 设定初始蜜源和引领蜂个数为EB, 跟随蜂的个数为OB,OB=EB, 则种群总数NP=EB+OB, 蜂群算法首先按照(1) 式随机生成含有EB个蜜源的初始种群。

被抽象成解空间中的点, 式中Xi,max和Xi,min分别代表解的上下限,i(i=1,2,…EB) 代表蜜源的编号,D代表解的取值空间,n代表问题的维数。蜜源Xi的质量对应于解的适应度值Fiti。

每个蜜源与一个引领蜂对应, 将引领蜂按照式(2)对蜜源位置进行更新

式中:xij(1<=i<=EB,1<=j<=n) 为蜜源Xi的第j个分量位置。vij(1<=i<=EB,1<=j<=n) 为第i个引领蜂在蜜源Xi基础上产生新蜜源Vi∈D的第j个分量位置。rij是[-1,1] 上的一个随机数。Xkj为在群体EB个蜂源中随机选择的另一个蜜源。

所有的引领蜂完成式(2) 的运算后, 飞回信息交流区共享蜜源信息。跟随蜂根据引领蜂分享的蜜源信息,按式(3) 计算蜜源的选择概率

人工蜂群算法的软件实现框架如图(1) 所示。

3 基于增强跟随蜂和侦查蜂的改进人工蜂群算法

3.1 基于引领蜂比例调整的改进

在ABC算法中, 引领蜂的作用是用来维持优良解的个数, 跟随蜂用来增强收敛速度, 侦查蜂用来跳出局部最优解。在基本的ABC算法中, 引领蜂和跟随蜂都采用相同的方式进行探索来寻找更优的解。所不同的是引领蜂是对所有蜜源都进行一次随机搜索,寻找更优解;而跟随蜂是在一定的概率引导下选择蜜源进行搜索, 这样当跟随蜂进行搜索时,并不一定每个蜜源都进行了搜索,而有的进行了不止一次的搜索, 跟随蜂能够对种群中相对优质解进行优先探索, 从而尽快找到质量较高的蜜源。

搜索过程中,引领蜂和跟随蜂进行搜索都是按照(式2) 进行, 对某一维随机的与其他引领蜂进行交叉。这样如果引领蜂太少, 由于参考系过少, 即使有很多跟随蜂也只是在相对较少的区域内搜索,容易陷入局部最优解,使算法进化停滞, 空耗计算时间, 影响进化速度。如果在后期增加引领蜂的比例, 可以使蜂群能够有更多的参考空间进行探索。

本文中, 在算法前期, 将跟随蜂的比例相对调高,能够增强优先探索相对优质解和跳出局部最优解的速度, 使算法的收敛速度增加。即使此点为局部最优解,也能够尽快跳出。在运算过程当中, 再逐渐对引领蜂比例进行增加, 能够使跟随蜂有更多选择和进化空间, 加强后期的探索能力。

由图中可以看出, 当引领蜂个数大于等于5 以后函数优化过程会比较平滑, 甚少出现早熟收敛现象。

通过大量实验比较, 当引领蜂处在种群总数的1/6至1/3, 但最少不能少于5 只时,ABC算法相对稳定,较少出现陷入局部最优解的情况。

将ABC算法中引领蜂在初始阶段采用NP/6, 再依据当前循环次数r按照式(4) 逐渐增加引领蜂, 当到Max Cycle/2 时增加到NP/3, 提高前期收敛速度和后期探索能力。

3.2 基于已抛弃蜜源的改进

在蜂群进行探索时, 各引领蜂是逐渐逼近全局最优解的, 所以即使是对于由于进化停滞被抛弃的蜜源也带有一定的解的信息。当有侦查蜂Xs出现时, 对已抛弃蜜源进行记录并计数(number of Scout bees,NS), 将所有已抛弃蜜源按照适应度值进行加权平均式(5), 这样可以直接将引领蜂带到全局最优解附近。为了消除局部最优解的影响, 对侦查蜂采用间隔使用加权平均的已抛弃蜜源和全局随机蜜源, 增强蜂群的开发能力。

式中:Xs代表侦查蜂位置,NS代表现在已经出现的已抛弃蜜源的个数,Xi代表各已抛弃蜜源,fiti代表各已抛弃蜜源的适应度值

综合上面2 方面的改进, 本文提出提出自适应调整跟随蜂和引领蜂比例的动态种群分配人工蜂群算法(OS-ABC)。

3.3 OS-ABC算法步骤

本文提出的OS-ABC算法步骤如图4。

4 实验仿真

下面为验证本文改进蜂群算法侦查蜂个数设置的效果, 选用单峰函数Sphere、Schwefel和具有多个局部最小点的多峰函数Rosenbrock、Griewank、Rastrigin、Akley做仿真实验, 实验采用EB=15,EB=45,soaABC[9],OS-ABC四种算法进行比较, 每个函数每个算法都独立运行30 次。实验仿真中参数具体设置为: 种群大小取90, 测试函数都取30 维, 控制参数limit为1000, 最大循环迭代次数Max Cycle取为5000 次, 仿真结果如表(1) 所示, 函数的进化过程曲线如图(5) 所示。

以上实验表明, 改进的人工蜂群算法OS-ABC具有较好的前期收敛速度和后期探索开发能力, 当函数优化后期初始ABC算法已经停止进化的时候,OS-ABC仍能够继续进化, 得到更精确的全局最优解。

5 结束语

针对蜂群算法前期收敛慢,后期探索能力差的问题,本文通过理论分析和仿真验证, 采用调整引领蜂的比例和改变侦查蜂的生成方式, 使算法能够尽快收敛, 且在后期有较强的探索能力, 有效避免早熟收敛。本文进行了仿真验证, 结果表明此方法有较好的改进效果。

摘要：针对人工蜂群算法中前期收敛慢,后期探索能力差的问题,本文通过分析引领蜂数量对算法寻优能力的影响,提出自适应调整跟随蜂和引领蜂比例的动态种群分配人工蜂群算法。在侦查蜂阶段,利用已抛弃蜜源信息进行加权平均,生成优质潜在解,该策略能够提高算法后期探索效率和搜索精度。实验表明动态种群分配人工蜂群算法具有收敛速度快、后期探索开发能力强,有效避免早熟收敛。

关键词：人工蜂群算法,动态调整,种群分配,已抛弃蜜源,优质潜在解

参考文献

[1]B.BASTURK,DERVIS KARABOGA.An Artificial Bee Colony(ABC)Algorithm for Numeric function Optimization[J].IEEE Swarm Intelligence Symposium2006Indianapolis,Indiana,USA.(5):12-14.

[2]D.KARABOGA,B.BASTURK.On The Performance Of Artificial Bee Colony(ABC)Algorithm[J].Applied Soft Computing,January 2008,8,(1):687-697.

[3]D.KARABOGA,B.AKAY,A Comparative Study of Artificial Bee Colony Algorithm[J].Applied Mathematics and Computation,2009,(214):108-132.

[4]秦全德,程适,李丽,史玉回.人工蜂群算法研究综述[J].智能系统学报,2014.4,9(2):377-385.

[5]ZHU,G.,KWONG,S.,Gbest-guided artificial be ecolony algorithm for numerical function optimization[J],Applied Mathematics and Computation,2010,217(7):3166-3173.

[6]B.AKAY,D.KARABOGA,Parameter Tuning for the Artificial Bee Colony Algorithm[C],1st International Conference on Computational Collective Intelligence-Semantic Web,Social Networks&Multiagent Systems[C],2009,5-7,Wrocław(Poland).

[7]D.KARABOGA,B.BASTURK,A powerful and Efficient Algorithm for Numerical Function Optimization:Artificial Bee Colony(ABC)Algorithm[J],Journal of Global Optimization,2007,Volume:39,Issue(3):459-171.

[8]肖剑,周建中,张孝远等.基于Levy-ABC优化SVM的水电机组故障诊断方法[J].振动、测试与诊断,2013,(5):839-844.

[9]易正俊,韩晓晶.增强寻优能力的改进人工蜂群算法[J].数据采集与处理,2013,(6):761-769.

高位动态遥感影像可视化算法研究 第2篇

高位动态遥感影像由于其亮度范围高于普通遥感图像,普通设备无法直接显示.利用基于分段线性变换算法实现了其可视化. 实验证明,此方法是一种快速、有效的可视化算法.

作 者：李山山 彭�� 孙小芳 郝君 LI Shan-shan PENG Man SUN Xiao-fang HAO Jun 作者单位：李山山,彭��,LI Shan-shan,PENG Man(安徽理工大学地球与环境学院,安徽,淮南,232001)

孙小芳,SUN Xiao-fang(福建闽江学院地理科学系,福建,福州,350108)

郝君,HAO Jun(温州市规划信息中心,浙江,温州,325000)

动态数据聚集算法探究 第3篇

【关键词】云计算；数据中心；动态数据聚集算法；绿色；能耗

【中图分类号】P33【文献标识码】A【文章编号】1672-5158（2013）02-0108-01

在网络技术的支持下，云计算利用集中构建的数据中心为客户提供高性价比的服务，包括计算、存储以及各类信息服务，为人类生活带来了极大的便利。然而，云计算数据中心的能耗相当大，该问题引起了人们的普遍关注，因此，需要通过改进算法，减少云计算数据中心的能耗，使其在提高计算效率和提高服务质量的同时，最大限度的降低消耗，使其向着绿色的方向发展。

一、 引起云计算数据中心能耗的原因

随着人们对云计算数据中心能耗问题的关注，需要采取有效的措施，最大限度的降低能耗，这就需要对引起能耗的原因进行分析，才能采取有针对性的措施，一般而言，引起云计算数据中心能耗的原因主要有以下三个方面：引起云计算数据中心能耗最大的是服务器设备、网络互联设备、电源供应设备等的数据中心主体所产生的耗能，并且在云计算数据中心的总体消耗中的比重最大。其次，是温控设备产生的内能耗，例如水冷、风冷的温度控制设备，该部分的能耗在总体能耗方面占的比重也很大，甚至有时候会超过数据中心主体设备的能耗，除此之外，其他设备产生的能耗虽然比较小，但是也不可忽视，对数据中心的总体能耗有着不可忽视的影响。

鉴于上述原因对数据中心的总体能耗产生重要的影响，需要对症下药，采取有效的措施，对云计算数据中心进行改进，提高其工作效率和服务质量的同时，最大限度的降低能耗，实现云计算数据中心的可持续发展。其中动态数据聚集算法便是一个有效减少能耗的算法，对云计算数据中心的绿色发展起了积极的推动作用。

二、动态数据聚集算法

（一）云计算数据中心的能耗分析

在云计算系统中，其能耗方面还存在着一些问题，造成了数据中心的高能耗，一般包括以下几点：首先是缺乏细致的温度控制体系，难以对当前的耗能进行有效的管理，这样就造成了较为严重的资源浪费，其次是在任务调度和数据部署方面的问题，忽视对能耗的关注和重视，只是关注到存储空间的大小和数据的访问问题。此外，对自然环境和对硬件的过度依赖也是造成耗能较高的原因，在降低能耗的工作中，基本都是从对硬件的本身功耗着手，但是往往结果很不理想，同时一些数据中心为了节约成本，将数据中心安置在较为寒冷的地区，避免人工制冷，但是如果设置在较为热的地区，需要进行人工制冷，加大了投入和消耗。当然随着技术的进步，数据中心的设备也不断改进，数据中心设备对温度的承受能力有了很大的提高，因此可以显著的降低能耗和电力的成本。

（二）云数据模型

从用户角度方面来说，在云计算系统中，云数据有着四种模型：第一类是用户在提出任务执行请求时，云计算就会根据对任务的分析，提供程序和数据计算，例如搜索引擎的应用；第二类是涉及用户任务的程序由用户提供，而数据是由云计算服务器提供，再在云计算的帮助下完成任务；第三类是用户提供数据，云计算提供程序和计算资源，服务器端在进行数据的迁移和处理，进而完成任务；第四类是用户提供任务涉及的程序和数据，利用云计算的计算和存储等硬件系统，完成任务。

对于前两类计算而言，系统提供的数据存储点对其有较大的影响，而后两种算法对系统性能的影响主要是受到数据迁移的执行点的影响。

（三）算法概述

为了提高服务的质量，需要云数据中心能够承受服务高峰的负载，以便满足用户的需求以及保持系统的稳定性，因此在对系统进行设计时，需要留有余量，这就需要借助冗余机制，进而避免了在非高峰阶段的能耗问题。同时由于数据中心的每一个节点在时间和负载不同的情况下，难以对温度进行精确的控制，这就会影响到制冷的效率，这就需要建立热力学散热模型，从而达到精确制冷的目的。

该算法是将数据和节点进行有序的聚集或者是重新的分布，进而实现对云数据中心的计算存储节点的有效利用，同时还可以使未利用的节点处于休眠或者是关机的状态，同时温控设备处于待机或者是关闭的状态，这就对绿色节能目标的实现起到了积极的促进作用。

计算与存储设备上包含了节点资源管理、节点控制、数据迁移、访问记录管理模块和节点运行监测模块；温控系统包含了环境监测和温控设备控制模块。其中温控系统与计算设备协同工作，特别根据节点运行监测模块和环境监测模块感知的情况，再利用温控设备控制模块来决定温控设备是否开启以及开启的程度，使得温控系统可以实现数据中心各区域的精确温度控制。

该算法具有明显的优势，对实现云数据中心的绿色节能起到了积极的促进作用，一方面在对数据和节点聚集以后，导致了部分区域节点的工作负荷和耗能的增加，这样就使部分区域避免了处于待机空转的状态，这样就无需对该区域进行制冷降温，进而降低了整体的耗能。另一方面数据聚集以后，在系统运行中，节点是处于高负载状态的，大大的提高了资源的利用率，在相互备份的支持下，可以实现对数据的不间断访问，这样就使云计算数据中心的运行得到了保障。此外，利用动态数据聚集算法，可以实现各个节点的轮转运行，极大的提高了硬件设备的寿命以及设备使用的稳定性。

三、面向绿色云计算数据中心的动态数据聚集算法分析

动态数据聚集算法中，节点始终处于工作、待机和关机的状态，这就需要根据其状态，采取相应的节能措施。在节点待机时，其CPU和硬盘是处于基本不工作的状态的，但是节点仍然有损耗，这就需要对数据进行有效的部署和调度任务，减少处于待机状态的节点数量，避免节点引起的空耗。当处于关机状态时，电源线的能耗基本可以忽视。

（一）性能分析

数据聚集前，数据部署比较散乱导致了访问热点的不规律，致使大量节点的利用率低，待机状态的能耗造成了环境的热负荷，这就加大了温度控制的工作量，造成了能源的浪费。而在对节点进行聚集后，消除了服务器的待机空转状态，所产生的热耗仅仅来源于电源线，同时温控设备也无需进行降温，最大限度的降低了能耗。

（二）资源利用与服务的质量

如果用户的请求规模相同，对资源的利用率不会有很大的差别，但是在具体节点工作而言，进行数据聚集后，节点在开机运行时，处于高负载的状态，大大的提高了利用率。同时，该算法利用运行规律相反的节点进行互补，避免了因为节点关闭而无法对数据进行访问的情况进而大大增强了系统的性能，并提高了服务的质量。

总之，云计算数据中心的节能与能耗控制是一个复杂的过程，需要多个方面的共同努力，需要分析多个因素和多个层面，这就需要从数据的部署和任务的调度方面着手，实现动态数据和节点聚集，对能耗的计算和温控能耗的控制进行统一的调度以及精确的控制，这样就降低了云计算的整体能耗，推动了云计算数据中心向着绿色节能的方向发展。

参考文献

[1] 金海，吴松，廖小飞.云计算的发展与挑战[M].计算机学会，2011（09）

[2] 李静姝.浅谈云计算机的数据中心分析与研究[J].科技资讯，2011（07）

[3] 李腾.云时代集成系统的构建设想[J]计算机发展学刊，2009（11）

一种动态频谱分配算法 第4篇

本文主要研究如何合理规划与优化分配资源提高频谱复用效率问题。模拟退火算法 (SA) 作为局部搜索算法的扩展, 在每一次修改模型的过程中, 随机产生一个新的状态模型, 然后以一定的概率选择邻域中能量值的状态。这种采用新模型的方式使其成为一种全局最优算法, 并得到理论证明和实际应用的验证。

1 模拟退火算法

模拟退火的概念是根据熔融金属中粒子的统计力学与复杂的组合最优化问题的求解过程的相似性而提出来的。统计力学的研究表明, 在温度T, 粒子停留在状态r满足波兹曼 (Boltzmann) 概率分布

式 (1) 中E (r) 为r状态的能量;kb>0, 为Boltzmann常数;T为绝对温度, 量纲为1;Z (T) 为概率分布的标准化因子

在温度T时, 根据金属内部粒子的状态选择规律, Metropolis等提出了以下准则:设初始状态i为当前状态, 该状态的能量为Ei, 然后对该状态作随机微扰, 得到一个新状态j, 新状态的能量为Ej。如果Ej<Ei, j就为重要状态;如果Ej>Ei, 考虑到热运动的影响, j是否为重要状态要根据固体处于该状态的概率来判断。固体处于状态i和j的概率的比值等于相应Boltmann因子的比值, 即

用随机数据发生器产生一个[0, 1]区间的随机数ε, 若r>ε, 则新状态j为重要状态, 就以j取代i成为当前状态, 否则仍以i为当前状态。再重复以上新状态的产生过程。在大量固体状态变换后, 系统趋于能量较低平衡状态, 固体状态的概率分布趋于Boltmann概率分布。

以上接受新状态的准则称为Metropolis准则, 相应的算法则称为Metropolis算法。SA中采用上述准则, 故成为全局寻优算法。

2 基于改进模拟退火算法的频率分配

2.1 模拟退火算法模型扰动

SA中新模型的产生是对当前模型进行扰动得到的, 常规用的是高斯分布法, 而快速模拟退火计划采用依赖于温度的似Cauchy分布法, 即

式 (4) 中:mi为当前模型中第i个变量;u为[0, 1]内均匀分布的随机数;[Ai, Bi]为mi的取值范围;m'i为扰动后的模型中第i个变量, 且m'i∈[Ai, Bi]。

Cauchy分布产生新模型的优点是:在高温情况下搜索范围大, 在低温搜索时, 仅在当前模型附近有一平坦的“尾巴”, 使其易于迅速跳出局部极值。这一改进加快了SA的收敛速度。

2.2 改进接收概率

由广义Boltmann-Gibbs分布, 可给出新的接收概率计算公式

式中:ΔE=E (m1) -E (m0) 。h为实数。当h→1时,

这是常规SA的接受概率公式, 为式 (6) 的特例。

2.3 基于改进算法的频率分配

基于改进模拟退火算法的频率分配算法步骤如下:

(1) 给定初温t0, 随机产生解Fold, 计算代价函数Cold;

(2) for k=1 to NUM loop

(3) 结束, 输出最优结果。

为证明频率分配方法的有效性和普遍性, 初始解在可用频率资源中随机生成。

通常SA算法应用于频率分配时, 新状态采取随机产生的方法, 这确保了全局收敛性能, 但也导致后期搜索速度慢;因此根据破坏约束的已有信息建立新状态, 有利于加速SA算法的收敛速度。新状态按如下步骤进行创建:

(1) 在计算代价函数的同时, 记录每个违反约束条件中任意一个频点, 已记录过的就不重复记录;

(2) 在以上违反约束频率记录的基础上, 从每个频率集Fi中随机抽取两个频率 (对应于频率表长度为32和64时) ;

(3) 从频域Φ未分配的频率中随机选择步骤 (1) 和步骤 (2) 中记录的数目一样多的频点数;

(4) 将步骤 (3) 中选择的频点随机替换步骤 (1) 和步骤 (2) 中记录的频点, 即完成新状态的建立。

可以看出, 新方法采用一定程度上的确定性转移规则, 同时保证一定的随机性, 可比普通SA算法更有时间效率。

当算法运行中满足下列任何一个条件时终止算法:

(1) 温度tk降低到指定的tmin。

(2) 循环次数超过最大迭代次数 (设为50次) 。

(3) 代价函数C=0。

3 实例验证

在某网络规划软件中, 需要进行频率分配, 跳频组网的参数由用户自行决定, 并在Visual Studio2010应用程序控制台上进行手动输入, 这也造成每次算法运行所得结果本身具有一定的随机性。

初始频率分配方案跳频同步干扰概率:

为验证频率分配方法的性能, 对频率表长度为32、跳频子网数量分别为4、6和8的情况下频率表进行频率分配求解。跳频电台处于发射状态的概率α=0.1, 电台中频频率为70MHz, 跳频频段为30MHz~90MHz, 跳频间隔为25k Hz, 共2400个频率点。假定每个跳频频率表的第6位为同步信号频率;射频跳频滤波器30d B带宽为中心频率的6%。

仿真中, SA算法初温t0=100, 冷却参数δ=0.98, 终止温度tmin=1, 循环最大迭代次数为50次。为分析跳频同步信号特殊约束对跳频通信同步性能的作用, 对跳频同步信号频率未采取特殊约束的情况也进行了求解。跳频通信系统频率分配优化前后干扰概率的求解结果如表1所示。

通过上表能够看出, 对跳频同步信号采取特殊约束, 可以明显减小跳频同步信号受干扰的概率。即使是在同址干扰最严重的情况下, 即8个子网均采取全频段跳频方式, 采用跳频同步信号特殊约束后, 同步信号被干扰的概率也只有0.0012%, 远远优于未采取特殊约束时0.0653%的同步信号被干扰概率。采用跳频同步信号特殊约束可以在基本不影响频率分配总代价函数的基础上显著减小跳频同步信号受干扰的概率, 其实质是在同样破坏约束的情况下, 尽可能避免该被破坏约束中的被干扰信号为同步信号, 这样就能提高同址跳频通信系统的同步性能。

4 结语

在无线通信领域中, 网络的合理规划和优化是十分重要的现实问题。在电磁环境相当复杂的无线通信中, 这一问题尤为突出。频谱分配的前提和基础是场强预测、电波覆盖是否合理、正确, 这关系到通信间干扰分析、频率指配的可靠性, 最终决定有限频率资源利用的高效性、科学性。

摘要：针对机动通信网络, 提出一种效能评估算法, 研究了效能评估指标体系, 包括基本通信能力、通信保障能力、互连互通能力、安全保密能力、抗毁顽存能力、机动快反能力、动态变化能力、快速自适应能力。首先明确任务需求, 确定效能参数, 构建效能评估模型, 获取数据, 研究效能评估方法, 选择合适的评估算法, 估算模型参数得出评估结果;最后通过实例说明频谱分配在特定应用场景下的效能评估。

关键词：模拟退火,效能指标,模型参数,权重系数,层次分析法

参考文献

[1]Bo Lennselius and Rydstrom.Software Fault Content and Reliability Estimations for Telecommunications System[J].IEEE Trans.Selected Areas in Communications, 1990, 8 (2) :262-271

动态资源分配算法 第5篇

摘要：针对动态目标的GPS定位精度不高和实时性较低的问题，通过改进卡尔曼滤波的定位算法，有效消除GPS动态数据的随机误差，给出了仿真得出的运动轨迹对比图和误差曲线对比图.该算法将速度观测量加入到常规的卡尔曼方程中，得出带约束项的改进型卡尔曼方程.通过实验结果可以看出该算法可以有效提高动态目标的GPs定位精度和实时性，具有重要的理论和实际意义.

关键词：动态目标；GPS定位；卡尔曼方程；约束项

Dol：10.15938/j.jhust.2016.04.00l

中图分类号：TN966

文献标志码：A

文章编号：1007—2683（2016）04—0001—06

0引言

全球定位系统（GPS）自1973年首次由美国国防部部署开始，凭借自身的高效益、高精度、自动化、全球性、全天候等显著特点，被广泛应用到大地测量、工程测量，水利、电力、交通、资源勘探和航海等领域中。

由于GPs的现代化进程飞速发展，其应用的范围越来越广泛，对其精度和速度也有了更高的要求.通过文献查阅可知，GPS动态定位一般可以分为伪距动态定位和载波相位动态定位.伪距定位平面坐标的精度可以最小可以达到0.48 m，载波相位定位平面坐标精度约为O.004m，但目前在GPS定位算法方面的研究还很不足，在滤波的过程中所用到的定位方程运算复杂，计算量很大，定位的精度低，速度慢，不适用于对动态目标的定位，本文对定位算法进行改进，通过分析GPS接收机的定位结果，设一个误差总和，其包含各种误差因素，由于定位的精度会受到速度观测量的影响，现将速度视为约束条件的卡尔曼方程与将速度视为观测量的常规卡尔曼方程联立.可以提高定位的精度和实时性，简化方程，减少计算量，对于GPS定位算法的发展而言，具有重要的理论和实际意义。

1.GPS定位误差分析

GPS为导航定位、测量和测量学开辟了一个崭新的时代.但由于GPS定位中含多种误差，利用传统的方法很难将其影响去除，使得GPS在某些场合的应用还受到限制，GPS定位的主要的误差源包括：①卫星测量误差.可分为：卫星时钟误差、星历误差、电离层的附加延迟误差、对流层的附加延时误差，②卫星的几何位置造成的定位误差，在运动目标定位中误差主要源于如下几种：多路径效应、信号遮挡、信号丢失、GPS接收机动态测量范围的局限性而引起的定位误差及首次定位的时延误差等。

影响GPS定位结果的误差因素也同时影响其测速情况，不过，接收机误差因素的影响表现显著，其他因素影响稍弱.接收机误差因素中接收设备的锁相跟踪环路掺人噪声，产生虚假的多普勒频移是其主要影响GPS测速的因素。

2.观测速度量的GPS定位算法

将误差因素均看成零均值的高斯白噪声，而实际情况中，很多信号显示为非白噪声分布.为了能提高GPS对于动态目标的定位精度和稳定性，对其信号的处理方式选用了卡尔曼滤波（kalman filter）算法.其原理是根据信号的前次估计值和当前观测值，通过利用线性无偏最小方差估计准则来推算得出当前的信号值，无需考虑以往观察值.还需已知状态方程、量测方程、白噪声激励的统计特性、量测误差的统计特性，其所用的信息均是属于时域内的.卡尔曼滤波适用于多维，其适用范围十分广泛，其特点有以下4种：

1）可以通过计算处理随机信号.

2）可以区分出所用被处理信号是否有用和干扰。

3）利用系统的白噪声激励和量测噪声的统计特性进行估算，不将其滤除。

4）算法属于递推类型，且在时域内使用状态空间法，适用多维随机过程。

卡尔曼滤波只利用信号的前次估计值和当前观测值，就可以对其进行线性无偏最小方差.

由于动态目标在运动过程具有复杂性，根据常规滤波方程处理可以发现其过程复杂、计算量大、实时性低等缺点.在实际使用的情况下，通过在GPS接收机上接收到的定位坐标进行预处理，并将所有的得到的误差加和计算.达到简化方程；减少数据处理量；减少得到的运算结果延迟性和准确性的目的。

2.2基于速度量的算法改进

2.2.1状态方程

在定位的实际应用中主要考虑平面的位置情

2.2.2改进后量测方程

比较GPS定位的速度数据和位置数据可得，其原理不相同，准确性则不同，速度数据的准确性高于位置数据的准确性，GPS定位过程中会输出的动态目标位置信息和速度信息，其中速度信息可分为速度的大小和方向，速度观测量影响GPS的定位精度，在观测方程中加入速度观测量可以提高定位精度，提高状态的可观测度。

将约束方程代人卡尔曼模型中，使得原本的卡尔曼方程的状态参数不满足新的条件方程。需要对其进行相应的修改，实现准确的滤波推导.根据采用最小方差估计原则，推导出新的带有速度约束条件的卡尔曼递推方程，并且保留原有发状态参数.

建立拉格朗日方程：解之得：最后得到带速度约束条件的卡尔曼算法递推公式：

它与常规的卡尔曼递推算法进行比较，改进后卡尔曼算法在预测值后加了一个和约束条件有关的修正项，没有对其他步骤进行改变.修正项是表示为最大化符合速度约束条件的要求，不间断的对载体运动的轨迹进行修正。

3.改进后算法仿真与对比

我们设定某一目标的起始位置在坐标轴的（0，0）上，本目标在x和Y轴上的初始加速度均为O.1m/s，设定本目标在坐标系内的运动为非规律运动，并且x和Y轴上分别给加速度增加了噪声影响，并且可以得到运动目标的运动轨迹.通过设定两部对目标进行实时测量的观察机以用来得知目标的相对距离.假设运动目标的状态向量、观测向量分别是：

随后我们使用标准型卡尔曼方程对运动目标的轨迹进行滤波处理，其中它的系统噪声和量测噪声都是非相关独立高斯白噪声，其中设定时间T为1秒，在第3个历元介人滤波.全部过程耗费300秒，可以得到运动目标的轨迹如图1所示。

通过卡尔曼算法得到的值同真实轨迹值相减，求得滤波的误差曲线.如图2所示为其x轴上的误差。

通过以上的方式，替换量测方程为线性方程，使用改进后的卡尔曼算法再次进行仿真，得到的运动目标轨迹如图3.

通过图1和图3对比常规卡尔曼算法得到的轨迹和改进后卡尔曼算法得到的轨迹，可以看出后者更接近真实轨迹.通过图2和图4对比常规卡尔曼算法得到的误差曲线和改进后卡尔曼算法得到的误差曲线，可以看出后者误差明显减小.其原因是在相同条件下，改进后卡尔曼算法是将速度观测量代入状态变量中，并且作为速度约束条件代入卡尔曼方程，在系统方程不变的情况下，改进后的量测方程转换为：

而后利用Z₁和Z₂可以得到常规卡尔曼方程以及带约束项的卡尔曼方程，而后通过之前的运动轨迹模型在矩阵实验室中进行仿真，如图5和图6所示。

通过对比图可以直观得到带有速度约束项的改进后卡尔曼方程是很有效的降低了误差度.其误差值给出了比较有代表性的，如表1所示.

其原因为观测速度量的加入约束了状态量的变化，使物理意义与数学关系结合的更加直接，其改进后结果对预测值进一步进行了修正.这么做的优点是提高了坐标精度，得到的图像也证明了此点.综上所述：带有速度限制算法的卡尔曼量测方程能提高预测精度。

4.结论

动态资源分配算法 第6篇

无线资源是有限的,而用户的需求是无限的。由于无线信道的时变性,因此高效的调度算法对于提高系统的吞吐量和用户的稳定性具有重要的作用。从网络的角度来说,这种系统可以转换为一个多用户多服务器系统,每个服务器代表一个子信道。由于在每个时隙一个给定的服务器只能为一个用户服务,因此本文要解决的就是多个用户竞争一个给定的服务器的问题。系统模式如图1所示。

图1中,基站将要传输给每个用户的数据包都先存储在一个相应的缓存区队列中,图中Qi表示要发送给第i个用户的数据包存储队列,Ai(t)表示在时刻t到达队列i的数据包的个数,S表示给定的单个服务器。由于信道的衰落,每个队列和服务器之间的连接是随着时间而变化的,连接状态用一个二进制连接变量Ci(t)表示。最终要解决的问题就是当与服务器S处于连接状态的多个队列竞争服务器S时,到底要将服务器S分配给哪一个队列[2]。最终目标就是设计一个高效的资源分配算法不但要提高网络吞吐量,而且还要保证用户的服务质量。

在此队列模型中服务器的分配是可以控制的,网络控制者在做分配决定前知道队列的长度。在每个时隙可能根据对队列历史状态的观察和之前的分配情况来决定现在的分配,分配政策首先要使系统稳定,其次要最大限度的提高网络吞吐量,降低延迟,保证用户的服务质量。本文是用李雅普诺夫最优化的理论设计一种基于队列积压和延迟的动态资源分配算法,这种方法既维持了网络的稳定性,将队列积压降低到一个最小的阻塞状态,降低了延迟,又提高了吞吐量,而且在吞吐量和延迟之间设置了一个很好的均衡。

2系统模型分析

2.1系统模型描述

系统模型如图1所示,用Q(t)=(Q1(t),...,Qn(t))表示每个队列在时隙t的队列积压(数据包的个数),假设每个队每个队列的数据包的个数。假设A(t)独立同分布,且E{A(t)}=@(λ1,...,λn)。用C(t)=(C1(t),C2(t),...C3(t))表示服务器S与队列连接的状态矩阵。在时隙t,若Ci(t)=1则表示队列Qi与服务器S处于连接状态(信道状态处于ON状态),若Ci(t)=0,则表示队列Qi与服务器S处于断开的状态(信道状态处于OFF状态)。用µi(t)表示在时隙t为用户i成功服务的数据包的个数,则队列的动态更新方程如下[3]:

要使整个系统稳定,则所有队列在时间平均的意义上必须满足以下条件:

2.2时变的链路可靠性

假设服务器在每个时隙至多可以传输一个数据包,则µi(t)∈{0,1}。用x(t)=(x1(t),x2(t),...,x3(t))表示传输矩阵,xi(t)∈{0,1},若xi(t)=1则表示服务器S在时隙t要对队列Qi进行传输,假设x(t)来自所有可允许的传输集合X,x(t)∈X。传输矩阵x(t)和服务器的状态矩阵C(t)联合决定每个时隙服务器成功分配的概率,用以下所示的可靠性函数表示:

可靠性函数Ψi(x(t),C(t))∈[0,1],表示在给定x(t)和C(t)时服务器S成功分配给队列Qi的概率。

在实际中,C(t)表示每个时隙信道估计的结果,这个估计可能不准确,因此用可靠性函数Ψi(x(t),C(t))表示实际网络中信道可以为用户队列传输的概率。假设ACK/NACK信息在每个时隙末会反馈给每个用户队列,已告知传输是否成功,没有传输成功的数据包继续存储在缓存队列中。

则服务变量表示如下:

假设给定当前的预传输矩阵x(t)和服务器状态矩阵C(t)时,在当前时隙t成功传输与否与过去的状态无关。

2.3最优化的目标函数

设计资源分配政策的最终目的就是使目标函数最优化,本文的目标函数如下所示:

式中,为效用函数,它是一个非负的连续的非递减的上凸函数[6]。其中yi(t)为用户i的吞吐量,定义如下:

式中,yi(t)为时隙t中用户i成功服务的数据包的个数。

定义为无线网络下行链路的网络容量区,定义为所有可获得吞吐量矩阵的闭集合。

3最佳资源分配政策

李雅普诺夫最优化理论是随机网络最优化的一种数学方法,此优化方法可以防止对信道状况预测不准确而带来的限制,它只需观察每个时隙开始时刻的信道状况,不像传统的基于预测的算法需要对信道状况做长期的预测。这种方法充分考虑了队列模型的动态效果,充分利用了队列的积压信息来做各种调度控制决定。

3.1算法设计思想

用Hi(t)表示在时隙t数据包到达队列Qi前端的等待时间,如果Qi在t时没有数据包,则定义Hi(t)=0。如果在t时一个数据包到达一个空的队列,规定在t+1时将其放置在队列前端。定义示性变量αi(t),如果Qi(t)>0,则αi(t)=1,反之为0。则数据包到达队列前端的等待时间Hi(t)的更新方程如下[4]:

式中,βi(t)=1-αi(t);Ti(t)为队列前端的数据包和后继到达的数据包之间的时间间隔。可以这样理解:如果αi(t)=0,则βi(t)=1,则队列Qi此时为空,此时仅且当仅有一个数据包到达时Hi(t)=1。相反,如果αi(t)=1,

则βi(t)=0。由于队列前端数据包和后继到达数据包之间的间隔Ti(t)可能大于或等于Hi(t)+1,在这种情况下,定义t+1时刻队列为空,则此时Hi(t+1)=0。

定义(t)[Q(t);H(t)],Q(t)和H(t)分别为方程(1)的值和方程(9)的值的矩阵,构建如下所示的李雅普诺夫函数:

将每个时隙所有队列的平方和定义为李雅普诺夫函数L(t),如果L(t)很小,则所有的队列都很小,如果L(t)很大,则至少有一个队列很大。因此李雅普诺夫函数是用其来衡量网络阻塞的标量。

定义((t))为李雅普诺夫一步漂移,其表达式如下:

如果在每个时隙做控制决定,贪婪的最小化∆(t),这样可以将队列积压降低到一个最小的阻塞状态,直观的维持了网络的稳定性。

V是一个非负的系统控制参数,用于调节延迟和基于吞吐量的网络效用之间均衡。在每个时隙做控制决定贪婪的最小化漂移-效用函数的值,这样既维持了网络的稳定性,又提高了网络效用。

3.2最佳资源分配算法

每个时隙t,观察Q(t),H(t)和C(t),按照下面的步骤做服务器的分配决定:

(1)选择一个传输矩阵x(t)解决以下最大化问题:

(2)队列更新:根据方程(1)和方程(12)更新队列。

4算法性能分析

定理1:假设存在ε≥0使λ+2ε1∈Λ,令Θ(t)=(Θ1(t),...,Θn(t)),假设E{L((0))}<∞,则在本文提出的分配算法下有:

如果ε≥0,则所有的队列Θi(t)的均值稳定。

如果ε>0,则所有的队列都稳定。

对上式两边当t→∞取极限得(b)证毕。

由式(12)得

则对i∈{1,...,n}有:E{Θi(t)2}≤2Bt+2E{L(Θ(0))}

由于|Θi(t)|≥0,则E{Θi(t)2}≥E{|Θi(t)|}2,则式两边同时除以t,并在t→∞取极限得。

定理2:假设所有的队列起初为空,令y*表示最佳的吞吐量的时间平均矩阵,则g(y*)=g*为最佳的网络效用,μ*(t)为最佳服务率,假设E{μ*(t)}=E{Ai(t)}=y*,系统控制参数V>0。

由定理2可以看出,增大系统控制参数V可以使基于吞吐量的网络效用无限接近于最佳值,但是由定理1可以看出增大V值可以增大队列积压值,从而增大延迟,所以在延迟和吞吐量之间形成一个O(1/V,V)的均衡,因此本文提出的分配算法选择合适的系统参数V至关重要。

5仿真分析

为验证本文所提算法的优越性能,我们使用吞吐量、延迟来评估系统系能,仿真工具为Matlab。仿真场景为50个用户的无线网络下行链路,调度间隔(slot)为1ms,在每个调度间隔数据包的平均到达率为0.5,信道处于on状态的概率为0.5。

我们首先将吞吐量和延迟视作V的函数,观察吞吐量和延迟与V的关系,V值变化范围为0到1000,仿真时间为1500ms。由图2可以看出随着V值的增大系统的平均吞吐量也不断增大并趋于饱和,同时系统的平均延迟,随着V值得增大线性增长,因此必须选择一个最佳的V值既使系统的吞吐量比较理想,同时又不会导致太大的延迟。由图2可知,选择V=120时,平均吞吐量等于0.397,平均延迟为105个slot,是一个很好的折中点。

其次,我们固定V值时,比较本文所提出的算法和随即分配算法吞吐量和延迟的性能,仿真时间为1000ms。随即分配算法就是将服务器随即分配给不为空的用户队列。图3将两种算法的吞吐量进行延迟,在仿真算法内本文提出的算法吞吐量比随机分配的算法高。图3给出两种算法的延迟的经验分布,可以看出本文算法和随机分派算法相比改善了延迟性能。

6结束语

本文针对LTE无线网络下行链路系统用户间对一个服务器竞争的问题,根据李雅普诺夫最优化理论,设计了一种动态资源分配方法——基于队列积压和延迟。本文提出的算法不但能优化吞吐量,还能减少用户延迟,实现两者均衡。

参考文献

[1]徐景,胡宏林,周婷.3GPPLTE标准化进展.中兴通信技术,2007,13(2):9-12

[2]谭伟,张文新,马雨出.LTE的无线资源管理.邮电设计技术,2007(3):62-64

动态资源分配算法 第7篇

随着应急指挥网络系统复杂程度不断提高,系统规模将越来越大。这就造成应急指挥系统中网络的规模越来越大,功能越来越复杂,加之网络攻击技术与计算机病毒,使得网络故障的发生是不可避免的,而且发生的概率会越来越大,网络故障诊断逐渐成为应急指挥系统的关键。目前采用的故障诊断技术及方法无法满足应急指挥系统故障测试与诊断的要求。这时就需要协同故障诊断技术为网络系统提供更完备的综合保障支持。协同故障诊断技术包括任务分解,任务分配和决策融合等环节[1]。该文重点研究了其中的任务分配,提出了基于改进合同网的Agent动态任务分配算法,有效地避免了网络的拥塞,提高了协同故障诊断效率。

2 动态合同网算法

本文将管理Agent替代合同网算法的管理者,将执行Agent替代合同网算法的承包商完成合同网算法在Multi-Agent协同故障诊断中的应用,如图1所示。

传统合同网在MAS中的直接应用缺点较多,该文根据传统合同网算法的缺点提出了一下几点改进:

1) 减小管理Agent发标量。建立Agent性能库,使管理者根据所注册Agent的性能进行发标,避免了管理Agent广播标书带来的通信拥塞。

2) 与蚁群算法相结合。为每个执行Agent完成某项任务建立相应的信息素,这样就可以形成正反馈,管理Agent就可以根据前期经验进行任务分配。

3) 任务结果评估。传统合同网算法没有任务结果评估,该文将任务结果评估纳入到合同网算法中来,实现了系统的反馈。

2.1注册Agent性能库

管理者对每个注册Agent的能力都有一个数据库,例如Agent i执行任务j的能力为Cap(i,j) 。有能力执行任务的Agent将其初始能力值设为1,没有能力执行任务的Agent将其初始能力值设为0,这样就以数据库中的表的形式建立了Agent性能库。

设置性能库的本质是为了让管理者能够将任务分配给能够胜任的承包商执行,以减少资源耗费。所以有了注册承包商性能库,就可以根据性能库分发任务,这样就避免了传统合同网算法使用广播带来的通信量大的问题,有效避免的通信拥塞。

在合同网算法里,没有绝对的管理者,也没有绝对的承包商,它们之间是相互转化的,所以每一个有注册承包商的管理者都有性能库,而且性能库分为两部分:一部分为管理部分;另一部分为执行部分(执行部分只有自己的性能),如图2所示。

2.2 Agent信息素

传统合同网算法在竞标阶段执行Agent只要发现自己符合任务要求就会向管理Agent发送竞标标书,而且管理Agent会对每一个标书进行评估,这样就会导致管理Agent的负载过大,影响整个系统的效率。该文从减小执行Agent投送竞标标书的数量的角度出发,提高了执行Agent的自主性和竞争性,引入蚁群算法的蚂蚁信息素,对可执行任务的Agent进行进一步的寻优。

当管理有一个任务要进行分配时,将会有若干个执行代理可以执行,所以就引出了最优问题。为了让任务分配趋于最佳合理状态,引入了蚂蚁的信息素,并将蚁群算法中的转移概率公式改进为所需的代理i执行任务j的效果概率公式,如下式。

其中Pij(t) 表示t时刻,代理i执行完任务j后,在所有执行代理中的执行效果优劣概率;τ(i,j) 为t时刻代理i执行任务j的信息素值;capable为能够执行任务j的代理的集合;T(i,j) 为t时刻代理i执行任务j的执行时间的倒数,即:

其中Tc为任务的完成时间;Td为代理i到代理j的延迟时间,单位毫秒(ms)。

依据以上公式(1)算出每一个执行Agent执行任务j的完成优劣的概率,概率越大,该Agent完成任务j的效果就越好。所以本文根据P?ij(t) 的大小选择概率大的执行任务j,这样既保证了任务的完成质量和效率,又减小了系统的通信量和负载。

针对算法中信息素和参数是动态的这一特点,为了保证全局寻优,该文利用轮转赌法选择出来的Agent执行任务。轮转赌法是模仿轮盘转动进行选择[5],如图3所示,将各Agent执行任务完成的优劣概率在赌轮上划分成扇形区域,然后转动轮盘,使其随机转动。当轮盘停止转动时,指针所指向的扇区就是所要选择执行任务的Agent。所以完成优劣概率大,被选中的几率就大。被选中的概率与完成优劣概率成正比。

利用上述的轮转赌法可以选择完成能力优秀的Agent来执行任务j,显著提高了任务完成的效率。如果通过轮转赌法选择的Agent没有完成任务,那么会继续通过轮转赌法选择Agent执行任务,直到任务完成为止。

当任务完成后,会执行对执行任务的Agent信息素进行更新,更新的公式为:

根据上述公式可以将信息素更新,这样就可以将完成能力优秀的Agent找出,并且也可以根据信息素的大小来判定执行Agent执行某一任务的效率。

2.3 算法描述

1) 算法的初始化阶段,将所有数据进行初始化,包括τ0,ρ,Q,Td。

2) 定期测试网络延迟,以此来更新延迟时间Tc;更新注册Agent性能库的性能参数Cap(i,j) ,管理Agent下的注册Agent会定期上报更新其性能参数Cap(i,j) 。

3) 管理代理根据注册Agent性能库来确定能执行任务的执行Agent。

4) 利用公式(1)计算已选Agent的完成概率,然后进行排序。

5) 利用轮转赌法在可选执行Agent中选择要执行任务的Agent,并在可选执行Agent表中去除,然后向执行Agent下发标书。如果执行Agent投标则跳到6),否则重复本步骤。

6) 管理Agent接受到投标的执行Agent分发任务,然后等待执行结果。

7) 执行Agent执行完任务后,上报管理Agent,并更新完成时间Td,并更新信息素τij(t) 。

2.4 算法的效率

假设一个Multi-Agent系统由管理Agent和n个执行Agent组成。传统的合同网采用广播式发送标书,则Agent之间进行一次通信所需要的时间设为Tm,管理者Agent的评估时间设为Tp,Agent完成任务的时间设为Tc。则传统合同网总的时间耗费为T1= 3Tm+ n Tc+ Tp。而改进后的评估时间Tj,因为能力库的建立只对由能力完成任务的Agent进行评估,所以将会大大减少评估的时间,虽然需要计算完成优劣的概率,但是相较于评估标书减少,对评估时间的影响极小。设改进后算法参加评估的Agent的数量为αn(0 < α < 1) ,则αn?Tj< n Tc;由于改进的算法采用了全局寻优策略,有效的运用了前期任务完成情况的经验,所以改进后算法的任务完成时间Tv< Tc;改进后算法与传统合同网算法相比加大的减少了管理Agent发送标书和执行Agent发送竞标标书的数量,所以系统的通信资源耗费较少,系统的整体负载较低,因此改进后算法的一次通信时间Tn< Tm。改进后算法的时间开销为T2= 3Tn+ αn Tj+ Tv,可以看出T2远远的小于T1。综上所述,改进后的合同网算法在效率上远远高于传统合同网算法。

3仿真分析

本文根据协同故障诊断的需求搭建了如下的仿真环境。该仿真环境共有10台计算机。其中由1台管理Agent计算机,1台交换机,10台执行Agent计算机。其中5台安装Linux,5台安装Windows XP。参数的设置为:a=1,b=5,r=0.1,Q=1000,tij(0)=1,Td= 500。

将仿真平台的所有电脑安装上带有专家系统的Agent,并建立为每个Agent建立能力数据库和信息素数据库。给予管理Agent一个由20个任务(例如:链路诊断,网卡故障诊断,交换机端口诊断等)组成的复杂任务,在这20个任务中有执行Agent可以执行有的不可以,每台电脑的执行时间也不同。最后按照传统合同网算法和动态合同网算法进行任务分配,对20个任务进行30次分配,仿真结果如图4所示。

从图中可以看出,改进后的合同网算法完成任务的总时间明显小于传统合同网算法,提高了任务分解的效率;改进后合同网算法的完成总时间波动性较小,增加了任务分解的稳定性。反观传统合同网算法完成任务总时间较大,且有较大的波动性,算法的效率较低。

4 总结

针对域间协同故障诊断中传统MAS任务分配算法的不足和传统合同网算法的缺点,提出了动态合同网算法,提高了算法的效率,仿真结果表明,该算法有效地避免了网络的拥塞,提高了协同故障诊断效率。但是,协同故障诊断中任务的决策融合研究的较少,将是下一步研究的重点。

摘要：随着应急指挥网络系统规模不断增加,网络故障诊断逐渐成为应急指挥网络系统的关键。针对域间协同故障诊断中的任务分配问题,提出了基于改进合同网的Agent动态任务分配算法,建立了Agent性能库,使管理者根据所注册Agent的性能进行发标,同时,为每个执行Agent完成某项任务建立相应的信息素,实验结果表明,该算法有效地避免了网络的拥塞,提高了任务分解的效率。

动态资源分配算法 第8篇

首次适应算法[1,2,3,4]。将可用内存块安置在空闲链表中,分配时总是从空闲链表首部开始查询,并将首个满足的内存块分配出去,该算法有效的保留了高地址端的大空闲区。缺点:在空闲链表的首部(物理空间的首部)容易产生大量的小碎片,且增加了下一次的查询次数。

循环首次适应法[1,2]。与首次适应法相似,循环首次适应法可以将产生的小碎片均匀的分布,有效地缩短了下次查询的时间,但是仍然没有有效地解决存储空间碎片化的问题,而且会导致缺少大的空闲分区。

最佳适应法[1,2,4]。最佳适应法可以有效保留较大的内存块,以满足用户对较大连续存储空间的需求,但是在内存中会产生更小的碎片。

最差适应法[1,2]。将空闲链表中的内存块按照大小顺序,逆序排列(由大至小)。可以有效地减少碎片的产生,但是内存分区会缺乏较大的连续存储空间。

快速适应法[1,2]。将空闲块按照大小进行分类,同时建立一张管理索引表,此算法在查询内存块时效率较高O(1),主要缺点在于合并内存块时,要遍历所有的内存块时间复杂度为O(n)。

伙伴系统[1,2,5,6,7]。已分配或未分配的内存区大小均为2的k次幂,其时间性能比快速适应算法差,但是由于采用了索引搜索算法,比顺序搜索算法好。而其空间性能,由于对空闲分区进行合并,提高了内存空间的可使用率,故优于快速适应法,比顺序搜索法略差。

哈希算法[1]。哈希算法就是利用哈希快速查找的优点,哈希算法具有较高的查找效率,在实际动态内存分配中使用广泛,但是在合并内存时需要逐个查找可用内存块并检查是否为可用的邻区内存。因此,实际开发中亟待需求高效的内存分配与合并算法。基于顺序搜索的动态内存分配算法的特点是管理简单,但效率不高。基于索引搜索的动态内存分配算法的特点是,分配效率较高,但回收效率较低。

两类不同的分配算法在不同的实际应用中有着各自的优势,但是在大多数的应用开发中普遍存在大内存块不易保留,内存碎片化,合并内存块时间开销大等问题[8,9]。multimap映射算法就是指将内存块的大小作为multimap的键,对应的值会记录内存块的地址信息以供分配[10,11]。该算法可以较好地解决上述问题,可以满足不同应用的需求。

1 改进的内存分配算法

基于multimap映射的动态内存分配算法采用C++的STL中提供的multimap关联容器,允许多个相同的键存在,键与值为一一对应关系。算法以内存块的大小作为键,内存块的地址信息作为值,以键值对的形式存储内存块的地址,并在内存块实体的首部与尾部添加标识信息。

1.1 内存分配算法

算法使用STL中multimap关联容器来存储Mcb(自定义的内存控制块)的地址信息。multimap提供了一种可以有重复键值的STL map类型。multimap<int,Mcb*>作为为容器的类型,以内存块的大小作为键,便于查询内存块。当用户申请内存时,通过multimap提供的方法去查询可供用户使用的内存块。使用lower_bound(k),upper_bound(k)可以得到一组指向键为k的元素的迭代器(在有多个相同键值对的情况下,分别指向元素的首端和尾端),如不存在则两个迭代器均指向首个大于键的值元素[11]。

为了避免产生过小的碎片,定义一个常量MIN_SIZE。如果切割内存块后会产生小于MIN_SIZE的碎片,则不再经行切割,直接分配供用户使用。

1.2 内存释放、合并算法

内存块在使用后,为了避免产生内存大量的碎片。需要在释放内存块时,尽可能地将物理空间连续的内存块合并到一起。在合并内存块时,需要遍历空闲内存以查找左邻块、右邻块,时间复杂度为O(n)[12,13,14]。为提高合并效率,本次算法采用边界标识法[2]。在内存块的首部和尾部添加一些信息(首部添加Mcb类型,尾部添加unsigned类型记录此内存块的大小)。添加边界标识的内存块信息分布,如下图1所示:

图1中的指针p,为返回给用户的可用内存块首地址。Is Available用于标识内存块的可用状态,size的大小为包括Mcb与后边界标志在内的大小。通过边界标识法可使合并内存块的复杂度为O(1)。

算法步骤:

在合并内存块时会查找左邻块、右邻块,当释放指针p的内存区域时会发生以下步骤:

(1)将指针P回退到内存块的首部,得到Mcb*mcb(使其指向内存控制块的首部)。

(2)检查当前指针是否在堆区域,指针不可越界。

(3)将mcb->availeble=1变为可用状态。4p sizeof(unsigned)

(4)将指针p继续回退sizeof(unsigned)个字节,读取左邻区的长度。再将指针p回退size-sizeof(unsigned)字节,经过强制类型转换,读取Mcb并判断是否为空闲状态,若是则将其从空闲multimap记录中删除,与左邻块合并后,并将左邻块Mcb中的size改为size+mcb->size,将合并后内存块的尾部标识改为size+mcb->size,将指向向左合并后的内存块,重复执行步骤(4);否则直接跳至步骤(5)。

(5)将指针p向右偏移mcb->size个字节,将指针强制类型转换为Mcb,读取available。若右邻块为空闲块,则将其从空闲multimap记录中删除,并与p当前指向的内存块合并,将mcb->size更新为mcb->size+size,右邻块的尾部标志的值改为size+mcb->size,重复执行(5)步骤;否则跳至步骤(6)。

(6)将合并后的空闲块添加到multimap中。添加至multimap中的内存块可能是与左邻块合并后的内存块,与右邻块合并后的内存块,或者是未合并的内存块。

边界标识法使得在合并内存时,可以通过偏移指针直接获取物理相邻的内存可用信息,所以可使合并内存块的复杂度为O(1)。

2 实验对比分析

数据准备:为尽可能的体现每种分配算法的特征(如,体现循环首次适应的特征,应当至少将内存块的分配循环一次),本次数据元素的选取,将参考实际应用中使用内存块大小的概率,产生若干数据元素以组成数据集合。本次实验环境为:Windows8操作系统,开发工具为vc++6.0。

在实际使用中,申请的内存块大小近似服从正态分布。本次模拟中,可供分配的总空间大小为10000个字节。参考实际使用情况,设定正态分布中期望与方差,可以得到符合实际且较为合理的数据集合[15,16]。

假设数据元素x~N(500,32400),μ=500,σ=180

按照概率随机产生23个样本,作为申请内存的指定大小,并从中随机选取6个元素用于释放内存[16]。通过计算可以得到不同大小的内存块使用的概率,以及取样数量,如下表1所示。

通过取样得到的数据集合为:

执行顺序:

分配内存时,按照Malloc集合中元素的顺序进行分配。在为528,604,345,523,621,494大小的内存块分配内存后,按顺序分别释放Free集合中的元素。

对比不同分配算法下的实验结果,比较不同尺寸空闲块数量,以及空闲块最值可以得到图2、图3:

注:P{0<x≤100}=0.0132,此区间内存块被使用的概率很小,所以将大小在(0,100]的内存块视为内存碎片。

编号1,2,3,4,5分别代表者首次适应法,循环首次适应法,最佳适应法,最差适应法,基于multimap映射算法。

通过图2可以看出,在不同尺寸空闲块数量的比较上,首次适应法与最佳适应法具有相同的结果。循环首次适应法与最差适应法产生大于200个字节的内存块数量较多,首次适应法、循环首次适应法、最佳适应法均产生了不同数量的内存碎片。multimap映射法没有产生内存碎片,且大于200个字节的内存块数目不多。

通过图3可以看出,首次适应法、最佳适应法在空闲块的最值比较上具有相同的结果,保留了较大的连续空间,同

时产生了难以利用的内存碎片。循环首次适应法、最差适应法未能保留较大连续空间,且循环首次适应法产生了内存碎片,但碎片尺寸大于首次适应法与最佳适应法所产生的碎片。multimap映射法保留了较大的连续空间,且未产生内存碎片。

由图2、图3的分析表明,multimap映射法在保留较大连续空间、减少内存碎片方面具有一定的优势。

不同的分配算法选取的数据结构可能存在一定的差异,通过分析不同算法所采用的数据结构以及具体操作的时间开

销,并参考图2、图3的实验结果。可以对不同内存分配算法的效率进行比较,从而得到具有更低时间开销的分配算法。整理结果可得如下表2:

由表2可以看出,在分配内存上最差适应法与multimap映射法具有较低的时间复杂度,分别为O(1)、O(log n)。在回收内存上multimap映射法的时间复杂度为O(1),优势较为明显。经综合比较可以发现multimap映射法在降低时间开销、保留较大连续空间、减少内存碎片方面具有较为明显的优势。

3 结束语

对几种动态内存分配算法进行分析与对比,可以看出选取不同的数据结构会对效率产生显著地影响。multimap映射算法通过红黑树的组织存储形式,提高了内存块的分配与回收的效率,通过边界标识法极大地改善了内存块合并的效率。虽然边界标识法是以消耗一定空间的方式来提升速度,但是当消耗的空间所占有效空间的比例较小时,是可以接受的。总体上,multimap算法较好地解决了大内存块不易保留,易产生碎片,合并内存时间开销大等问题。

摘要：对多种不同的动态内存分配算法的特点与优劣进行对比、分析,在兼顾效率和内存碎片率指标的要求下,提出了基于multimap映射的动态内存分配算法。该算法以内存块的大小作为键,内存块的地址信息作为值,以键值对的形式存储内存块的地址,并在内存块实体的首部与尾部添加标识信息。为检验算法效果,设计了多组数据对新算法和现有经典内存管理算法效率进行比较,实验结果表明新算法在降低时间开销,保留较大连续空间,减少内存碎片等方面具有较明显的改善。

关键词：动态内存分配,内存碎片,边界标识法,multimap

参考文献

[1]汤小丹,梁红兵,哲凤屏,汤子瀛.计算机操作系统(第四版)[M].西安:西安电子科技大学出版社,2014.

[2]严蔚敏.数据结构C语言版[M].北京:清华大学出版社,2007.

[3]Weinstock C.Dynamic Storage Allocation Techniques[D].Carne-gie-Mellon University,Pittsburgh,1976.

[4]池元武.嵌入式实时操作系统动态内存管理优化方案的研究[D].上海交通大学软件学院,2011.

[5]Peterson J L,Norman T A.Buddy Systems[J].Communications ofthe ACM,2007,20(6):421-431.

[6]姜立波.Linux内存管理分析与研究[D].电子科技大学,2011:46-58.

[7]王振江.提高堆数据局部性的动态池分配技术[J].计算机学报,2011(4):665-675.

[8]Stephenson C J.Fast Fits:New Methods for dynamic storage al-location[C].Proceedings of the 9th Symposium on OperatingSystems,ACM,1983.

动态资源分配算法 第9篇

1 列表着色算法 (list-cobring)

在图论模型研究中, 基于列表着色的频谱动态分配模型是实现在开放式无线通信网络中的频率动态指配的有效模型。它要实现的目的是在一定的约束条件下寻找最优的频段分配方案[1]。数学表达式如下:

约束条件:

其中, an, m是在满足所有约束条件下得到的可行频谱分配矩阵A中的元素。

研究列表着色算法的主要方法在分布式网络模型下主要有:贪婪算法、公平算法和机会算法。这三种算法所实现的目的是不同的:贪婪算法的实现目标是最大化地利用信道, 贪婪算法在分配频谱过程中, 首先将这个频谱分配给拥有边数最少的用户节点, 这样容易导致分配的不公平;而公平算法针对贪婪算法的不足, 从提高频谱动态分配的公平性着手, 对网络中的所有用户平均分配频谱, 但是通信开销较大;机会算法以减少运算量为基础, 进而提高通信系统的性能。

在实际的无线电环境中, 由于用户所处的电磁频谱环境的差异、所用调制技术的不同, 每个用户在同一个频段上获得的有效利益也是不一样的, 列表着色频谱分配算法没有考虑频谱效益和干扰带来的频谱差异, 而且实际使用过程中由于频率选择性的衰落, 用户之间容易产生干扰。

2 颜色敏感的图论着色算法 (CSGC)

颜色敏感的图论着色算法也是在图论模型的研究基础上, 针对list-cobring的不足, 通过分析不同调制、分配技术的不同之处, 综合考虑频谱效益差异性和干扰频谱的差异性, 相比listcobring算法, 它不仅使网络的容量得到了提高, 还明显减少了用户之间的干扰。它通过对运用多次迭代技术, 实现最大化利用信道和最大限度的公平性[2]。该算法的三种频率分配的最优效益函数分别为:

2.1 最大化带宽准则 (MSB)

其中, an, m是在满足所有约束条件下得到的可行频谱分配矩阵A中的元素, 取值为0或1, bn, m是引入的频谱效益矩阵B中的元素, 表示用户n使用频谱m所能获得的效益 (带宽) 的大小, 为满足条件的无干扰分配矩阵A的集合。在最大化带宽准则下, 它以系统达到最大的频谱效益为目标, 公式表示频谱分配给系统带来的最大带宽总和。

2.2 最大化最小带宽准则 (MMB)

它表示频谱分配使获得最小带宽的用户的带宽最大化, 目标是实现最大化受限用户的频谱利用率。

2.3 最大比例公平性准则 (MPF)

它以最大化每个用户间的公平性为目标, 实现频谱的公平分配。

CSGC算法实现的目的是全局最优分配, 在不考虑上次分配信息的情况下, 重新对每一个用户的频率使用进行分配, 因此运算量较大。在协作式和非协作式条件下, 基于效益和公平性的考虑, 可以通过制定协作式最大带宽 (CMSB) 和最大比例公平 (CMPF) , 非协作式最大带宽 (NMSB) 和最大比例公平 (NMPF) 准则。

3 局部议价算法 (local bargaining)

在实际的无线电系统中, 系统的网络拓扑结构是实时动态变化的。而CSGC算法主要用于静态的拓扑无线电网络系统, 如果在实际的网络结构发生变化时, 就需要重新设定网络的频率分配方案, 这样就造成运算量的增大。local bargaining算法根据上次频率分配的结果, 只需要对每次影响网络结构的细小改变做出相应补偿就可以完成频率的分配, 通信运算量就显著减少[3]。

系统网络拓扑结构发生改变后, 设定原有的最优分配矩阵是AN, M, 当有一个新的认知用户进入网络后, 分配矩阵变为两者的矩阵关系可表示为

如果是主用户k进入网络, 并且要使用频谱m0, 在主用户的干扰范围内的认知用户要及时退出该频段, 分配矩阵关系变为:

式中, Nbr (k) 表示受到主用户k干扰影响的所有认知用户的集合。

局部议价算法通过根据上一次的分配结果, 实现本次频谱的快速最优分配, 相对于CSGC, 减小了巨大的运算量, 但是如果上一次的分配不是最优, 会导致本次的分配结果的恶化。

4 并行分配算法

并行分配算法是在协作式最大带宽 (CMSB) 准则和非协作式最大带宽 (NMSB) 准则的前提下, 通过对相关矩阵的处理实现对模型图进行分解简化拓扑结构和降低图论着色的复杂程度[4]。

并行分配算法的思路构想是将模型图G= (U, EC.LB) 分解为多个子图, 同时对多个子图进行图论着色。因为各个子图都是简单图, 对模型图G的列表着色可以简化为对这些子图的点着色。根据频带正交假设条件, 对某个频带的使用不会干扰其他频带的使用, 在整个着色算法过程中, 各个子图着色相互独立, 不影响其他子图的颜色分配。相对于以上几种分配算法, 不仅不依靠以往的频谱分配结果, 而且大大减小了运算量。

参考文献

[1]Wei.Wang, Xin Liu.List-Coloring Based Channel Allocation for Open-Spectrum WirelessNetworks[C].Proceedings of The62nd IEEE Vehicular Technology Conference, 2005 (1) :690-694

[2]Zheng H, Peng C.Collaboration and Fairness in Opportunistic Spectrum Access[C].IEEE ICC2005 (5) :3132-3136

[3]L.Cao, H.Zheng.Distributed spectrum allocation vialocal bargainning[C], Proceedings of2005Second Annual IEEE sensor and Ad Hoc Communications and Networks (SEC-ON) , 2005:475-486

重视课堂动态生成资源 第10篇

一、差异型动态生成资源

美国哈佛大学心理学家加德纳的多元理论指出：“每个人都是具有多元智力的个体，智力之间的不同组合造成个体间的智力差异。”差异是不可避免的，教师如何面对差异是至关重要的，是置之不理，还是尊重差异，有效利用差异，直接关系到学生的学习效率。

案例一：

甲乙两车相对开出，甲每小时行a千米，乙每小时行b千米，经x小时两车相遇，两地相距（ ）千米？

生1：答案是：ax+bx

生2：答案是：（a+b）x

师：哪种答案对呢？

大多数学生同意第一种答案，只有一小部分学生认为第二种方法是对的。

师：再好好考虑一下。

生3：好像都对。（紧接着有一小部分学生响应）

师：谁来解释一下？

生4：第一种答案是甲乙的路程和，第二种答案是速度和乘时间，也是对的，因为时间相同，这种方法实际更简单。

世界上没有两片完全相同的叶子，更没有一模一样的两个人。正是学生不同的想法、不同的思路、不同的见解，才使课堂变得丰富多彩。教师备课时要做好预设，提前设想到课堂上学生可能出现的情况，不至于面对不同的想法手足无措。

二、错误型动态生成资源

心理学家盖耶认为：“谁不考虑尝试错误，不允许学生犯错误，就将错过最富成效的学习时刻。”教师应引导学生合理利用课堂生成的错误资源，而不是打击、排斥出错学生。

案例二：

学完平行与相交，老师出示立交桥的图片，提出问题：两条公路所在的直线是什么位置关系？

大多数学生：相交。

师：确定吗？

学生有些许疑惑。

师：谁来说说相交的定义？

生：同一平面内的两条直线能交叉在一起，有交点。

师：现在思考图片中两条公路是相交关系吗？

一小部分学生：不是。

师：为什么？

生：因为不在同一平面内。

课堂教学中，学生难免会犯错误，合理利用课堂错误资源，引导学生自己得出正确结论。这显然比直接给出答案更有效果，因为学生经历了自己的思考和同伴的交流，有了思维碰撞，会有更深的认识，还能保护“犯错误”学生的积极性。

三、开放型动态生成资源

在课堂上，由于问题情境的开放性，有时候学生不愿意沿着教师的预设走，他们热衷于自己所关心的话题，有时展开激烈的讨论时，完全背离本节课要学的知识。

教学“认识负数”时，出示信息窗情境图，我说：“吐鲁番盆地素有火洲之称。”学生突然兴奋起来：

“火洲，还火焰山呢。”

“好热，好热，热死人了。”

“我最爱吃吐鲁番的大葡萄。”

……

教室里一下子热闹起来，学生兴高采烈地讨论着对“火洲”的认识。

师：同学们都知道吐鲁番很热，但你知道吐鲁番的日温差很大吗？3月份平均最高气温在零上13°C左右，最低气温在零下3°C左右，你知道零上13°C和零下3°C是什么意思吗？怎样表示呢？

老师也没想到一个毫不起眼的“火洲”引起了学生激烈的讨论，如果老师不及时暂停就会完全脱离本节课的中心，但老师大大方方地沿着学生的价值取向，巧妙地引导学生回归正题，认识负数。

四、突发型动态生成资源

布卢姆曾说：“没有预料不到的成果，教学也就不成为一种艺术了。”课堂突发事件是每位老师都会碰到的情景，教师应开动脑筋巧妙处理，使之成为课堂的一种资源。

案例三：

教学“平行与相交”。

师：像这种在同一平面内，能交叉在一起的直线，称为相交。

生：香蕉。

哈哈哈，哇，香蕉啊，这两条直线真好吃，顿时班里乱成一团。

师：吃饱了吗？此相交非彼香蕉也。

师板书：相交。

师：想想我们喜欢吃的水果，这两条直线的位置关系记起来就简单多了吧，真是一群有想象力的孩子。

德国著名演讲专家海茵兹说：“用幽默的方式说出严肃的真理，比直截了当地提出更能为人所接受。”面对课堂上的突发情况，教师要注意保护学生的想象力与创造力，使学生在愉快的气氛中学习，这样往往会达到事半功倍的效果。

华师大叶澜教授在她的“新基础教育观”中，把“动态生成资源”表述为对教学过程生动可变的一种新概括。合理利用各种课堂动态生成资源，有助于因材施教，保护学生犯错误的积极性，也助于教师更全面地了解学生的优势和不足，进而有效地提高教学质量。

动态资源分配算法 第11篇

状态报告型DBA算法主要有C-DBA算法和T-DBA算法。其中基于T-CONT算法提出的C-DBA算法[6]能够保证高优先级的要求, 但在低负载条件下容易造成带宽浪费;基于Qo S的二层动态带宽分配算法 (T-DBA) [7]则同时为OLT和ONU端分配带宽, 在ONU端根据不同业务的优先级分配带宽, 并在OLT端把对带宽需求低的用户多余的带宽, 公平地分配给带宽要求高的用户, 从而提高了带宽利用率, 具备一定的公平性和灵活性, 但该算法在带宽不足的情况下, 优先级高的业务可能得不到足够的带宽, 从而增加了传输时延。

而非状态报告型即预测型DBA算法主要有基于小波分析的GPON动态带宽分配算法[8]和AR-DBA算法[9]。前者通过对网络流量进行预测, 获得ONU的实时带宽信息业务量, 为各ONU合理分配上行带宽, 从而能够保证各类业务的Qo S要求, 为GPON网络承载多业务提供了良好的性能支持, 但是具有较大的算法复杂度。而在AR-DBA中, OLT采用改进的AR模型对所有的数据流进行预测, 同时ONU不需要向上报告它们的带宽需求, 从而缩短了传输时延, 但这种预测模型过于依赖对某个周期内数据量的预测, 没有结合实时的传输数据情况, 因此预测结果存在较大的误差, 难以达到降低时延的目的。

状态报告型DBA算法都可以实现较为准确的分配, 但是开销大、时延高;而非状态报告型即预测型DBA算法虽然在一定程度上克服了前一种DBA算法的缺点, 但是存在较大的预测偏差。对此, 本文提出了一种结合流量预测的状态报告型算法TP-DBA, 它能够预测高优先级的流量, 有效地减少时延和丢包率, 从而提高网络的性能。

1 传统DBA的工作原理及分析

一个典型的GPON系统模型[10]由光线路终端 (Optical Line Terminal, OLT) 、光网络单元 (Optical Network U-nit, ONU) 和光分配网络 (Optical Distribution Node, ODN) 组成。GPON对带宽的分配包括两个方面:OLT对下面ONU中的上行带宽分配;在ONU内部对用户送进来的数据进行排队或调度的带宽分配。

本文仅讨论前一种动态带宽分配的方法, 其工作原理如下:

每个ONU实时地收集各个T-CONT缓存里的数据量和拥塞状态等信息, 并且根据BW Map中的带宽分配信息, 在规定的时隙内发送目前T-CONT中等待发送的数据状态报告。OLT收到该报告后, 经过DBA计算后更新BW Map字段, 并广播给所有的ONU, 收到广播信息的ONU在内部进行延时补偿运算, 制定出下个周期内发送数据的时间。这样的调度过程在GPON系统里进行反复循环运算。

以图1中的ONUi为例, t1和t3分别标记某个周期的起始和结束位置, t1和t2标记该周期内数据发送阶段的起始位置, t2和t3标记该周期发送阶段结束后至下一个周期开始之间的等待阶段的起始位置。在等待阶段内有许多数据将到达, 然而ONU的请求帧仅报告在t2时刻时队列中的数据量, 没有考虑那些即将到达的数据。因此, 该DBA中的请求帧不能实时反映出ONU的数据状态, 也就是说, 在等待时间内到达的数据需要等待至少一个周期才能被发送, 显然这会增加网络时延。

2 基于预测和分级轮询的DBA算法

2.1 流量预测策略

为了更好地描述预测策略, 定义如下参数:i用来标识ONU, 取值范围为1≤i≤N, N为ONU的个数;j用来标识周期, 取值范围为j≥1;t表示T-CONT类型, t∈{1, 2, 3, 4}, t=1表示T-CONT1类型, t=2表示T-CONT2类型, 依次类推;Pti, j表示ONUi在第j个周期的等待时间内预测将接收到的t类传输数据量;ARDti, j表示ONUi在第j个周期内实际接收到的t类传输数据量。

由于T-CONT1和T-CONT2对时延相对敏感, 因此ONU在发送请求帧前, 需要预测一个时间周期内即将到达的数据量, 以保证高优先级业务的性能。

预测机制如下:ONUi在发送请求帧前, 先计算缓存区中存储的数据量, 然后根据之前每个周期内接收到的数据量来预测本周期在等待时间内即将到达的数据量, 并根据预测结果确定请求帧中的数值。

在某个周期的等待时间内, 预测接收到的数据量的计算式为

式中:Ei, j-k是当前周期j之前的k个周期中k项数据序列的算术平均值;ΔARDti, j是ARDti, j和ARDti, j-1的差值;w1, w2, …, wk是权重因子。

一个周期的等待时间内到达的数据量和之前几个周期的等待时间内接收到的数据量之间有着密切的关系。为了保证预测的精度, 移动平均序列是逐步增加的, 而随着周期区间的增加, 预测和接收到数据量的相关性是逐步降低的。随着阶的增加, 实施所需要的代价也随之增加。如何不需要花费高昂的代价但同时能保证公式的良好性能, 经过多次实验, 本文采用一个四阶移动平均方法, 权重因子依次是0.4, 0.3, 0.2, 0.1。

2.2 分级轮询的DBA策略

Bti, j表示发送第j轮请求帧时, ONUi的数据缓冲区中存储的t类传输数据的大小;BWr表示当前的剩余带宽;BWtotal表示上行可分配的总带宽;Gti, j表示ONUi在第j个周期授予的t类传输数据量;Rti, j表示ONUi在第j个周期内请求的t类传输数据量。

第一步, 分配固定带宽, 固定带宽由具备高实时性需求的T-CONT1组成。然而在传统的算法中, 由于当前周期的请求帧内没有请求, 因此易造成严重的延迟。针对该问题, 算法中将预测在等待时间内到达的数据量并在请求帧中进行报告。因此, T-CONT1传输的授权是

更新剩余带宽, 得

第二步, 分配确保带宽。该类型带宽的分配包括两部分:一部分是T-CONT2中的确保带宽, 另一部分是T-CONT3中的确保带宽。

1) 分配T-CONT2中的确保带宽。在数据包存在延迟和吞吐量标准的情况下, 可以使用T-CONT2来作为可变比特率传输和应用, 因此在本算法中, T-CONT2有着和T-CONT1相同的预测方法, 因此T-CONT2传输的授权是

式中:Maxti, j表示ONUi在第j个周期内的t类T-CONT所能分配的最大确保带宽。

更新剩余带宽, 得到

2) 分配T-CONT3中的确保带宽。T-CONT3用于提供尽力而为的服务和最小带宽保证的服务, 因此T-CONT3传输的授权是

式中:Min表示每个周期内每个ONU的T-CONT3传输的最小确保带宽。

更新剩余带宽, 得到

第三步, 分配非确保带宽。非确保带宽由T-CONT3组成, 在为T-CONT3完成最小确保带宽分配后, 如果还有带宽剩余, 就为其进行非确保带宽分配。

更新剩余带宽, 得到

第四步, 分配尽力而为的带宽。T-CONT4用于提供纯粹的尽力而为的服务, 因此, T-CONT4的分配在其他高优先级的分配结束之后进行。如果在为T-CONT3完成最小确保带宽和非确保带宽分配后, 还有带宽剩余, 就为T-CONT4进行带宽分配

更新剩余带宽, 得

第五步, 如果此时BWr>0, 则根据刚更新的带宽需求表, 从第三步开始进行第二次带宽分配, 对没有满足要求的T-CONT分配非确保带宽或尽力而为的带宽, 如此循环, 直至带宽分配完毕, 退出循环。

最后, 整理各ONU中所有T-CONT获得的带宽数, 更新BW map表项。

3 仿真结果和性能分析

本文利用OPNET仿真软件, 搭建了测试的GPON网络拓扑结构, 用来对TP-DBA算法进行验证和分析。本文构建的GPON系统模型由1个OLT和16个ONU构成, 其中每个ONU都设置了4个队列, 分别对应信号源产生的4种T-CONT业务类型, 记为T-CONT1, T-CONT2, T-CONT3, T-CONT4。系统中上行和下行的链路速率为1.25 Gbit/s, 保护间隔时间为1μs, 帧大小分布在64~1 518 byte, T-CONT1到T-CONT4产生的数据流量比为1∶2∶2∶1。仿真采用冷启动的方式, 以下的仿真结果均是在OLT接收到的数据包数量达到300万个时产生的。

T-CONT1类型的数据包延迟如图2所示, 其中TP-DBA算法比C-DBA算法的时延略小。这是因为C-DBA算法保留了一个T-CONT1类型的固定带宽, 从而该算法的T-CONT1的性能可以得到有效的保证, 但是低负载时则会造成带宽的浪费。TP-DBA算法根据预测和状态报告进行带宽分配, 所以在低负载的情况下, 该算法可以较小的带宽确保T-CONT1的性能。

图3给出了T-CONT2业务类型在不同算法下数据包平均时延的对比结果, 可以看出TP-DBA算法在降低时延方面的性能要优于AR-DBA和C-DBA算法, 并且随着网络负载的增加, 这种优势更加明显。在低负载情况下, 另外两种算法的时延均约为1.5 ms, 而TP-DBA约为1 ms, 减少了约30%;在高负载情况下, TP-DBA的时延比C-DBA少25%, 比AR-DBA少50%, 甚至更多。这是由于TP-DBA算法对T-CONT2类型的预测机制减少了数据传输的等待时间。

T-CONT3和T-CONT4的时延比较分别如图4和图5所示。对于这两种业务类型, 由于TP-DBA和C-DBA的分配策略非常类似, 所以二者的曲线走向几乎一致。又由于TP-DBA算法为T-CONT1分配的带宽相对C-DBA来说较小, 因此它有更多的带宽用于T-CONT3和T-CONT4, 所以TP-DBA算法的时延比C-DBA稍小。

图6给出了从T-CONT1至T-CONT4的总体丢包率的对比情况。可以看出不论在何种负载条件下, TP-DBA的性能总是优于另外两种算法, 尤其在低负载的情况下, 这种优势更为明显。由于C-DBA仅是基于T-CONT的算法, 没有预测机制;而AR-DBA算法虽然引入了预测机制, 但缺少带宽请求报告, 因此两者的性能都受到了一定的影响。TP-DBA算法结合了预测机制和带宽请求报告, 从而能够更为精准地反映网络状况, 促使OLT带宽的分配更加合理, 丢包率更低。

4 结论

本文在对传统DBA的工作原理和现有的DBA算法进行深入分析的基础上, 针对动态带宽分配过程中存在的时延特性等问题, 给出了一种基于预测和分级轮询的动态带宽分配算法 (TP-DBA) 。该算法可以根据ONU缓冲区中数据队列的大小, 并参考前几个周期实际产生的数据量大小, 对当前的流量进行预测, 从而提高报告的准确性, 达到有效降低时延的目的。并通过仿真实验对TP-DBA算法进行了验证, 结果表明提出的TP-DBA算法能够有效地降低传输时延和丢包率。

参考文献

[1]王孝明.高宽带业务需求与宽带网络的演进[J].中兴通讯技术, 2010, 16 (3) :40-43.

[2]肖净敏, 赵振东, 薛海龙, 等.基于GPON系统实现综合业务接入的研究[J].通信技术, 2009, 42 (5) :147-148.

[3]韦乐平.光网络技术发展与展望[J].电信科学, 2008 (3) :1-6.

[4]王欣.GPON网络中MAC层相关技术的研究及DBA算法的设计[D].北京:北京邮电大学, 2007.

[5]ITU-T Rec.G.984.3, Gigabit-capable passive optical networks (GPON) :transmission convergence layer specification[S].2004.

[6]刘杨.GPON系统中一种高性能的DBA分配算法研究[D].上海:复旦大学, 2011.

[7]黄协.一种用于GPON中的动态带宽分配[J].接入网技术, 2005 (6) :58-59.

[8]嵇建波.基于多重分形小波GPON带宽分配算法[J].光通信技术, 2008, 32 (7) :15-17.

[9]LEE S K, JANG J W, BAE M H.Development and performance evaluation of a BR-DBA algorithm[C]//Proc.Third International Conference on Convergence and Hybrid Information Technology.[S.l.]:IEEEPress, 2008:1103-1108.