动态资源分配算法论文

动态资源分配算法论文（共10篇）

动态资源分配算法论文 篇1

雷达对抗在现代电子对抗中发挥着重要作用, 作战双方都千方百计保护己方雷达不被敌方干扰, 使得己方雷达发挥最大作战效能;同时作战双方也会设法利用先进的电子对抗技术去削弱敌方雷达系统的作战性能, 其中最为核心的就是运用各种技术手段干扰敌方雷达系统[1]。

电子战战场的情势复杂多变, 作战双方一般会选用多部雷达进行组网工作, 那么对方在实际战情中需要同时干扰的目标雷达可能为几部甚至几十部, 而作战双方的雷达干扰资源则是有限的, 如何能将有限的雷达干扰资源进行合理分配, 并且最终获得最大整体干扰效益就成了现代电子信息战争中一个决定战争胜败的重要问题[2]。

正是由于雷达干扰资源分配研究的重要性, 相关专家学者们进行了大量研究, 建立了诸多资源分配的方法模型。但是, 如何快速、稳定、高效地完成雷达干扰资源的合理分配仍是值得关注和研究的问题。任松等对雷达干扰资源的分配问题, 分析并设计提出了基于模糊多属性的动态干扰资源规划方案。沈阳等则运用0~1规划法, 给出了干扰资源优化分配的整体方案。吕永胜等运用Euclid贴近度的原理实现了雷达干扰资源的分配[3]。以上几种方法都是较为经典的组合优化算法, 适用于较小战情环境下的雷达干扰资源分配问题, 在目标雷达和干扰资源数量较大时将面临组合爆炸的问题。本文所提方法将一种动态选择概率的遗传算法应用于雷达干扰资源分配问题中, 由于概率的选择更加贴近雷达干扰的实际战情, 可以在收敛速度和干扰效果两方面取得较好的平衡, 使得对雷达干扰资源分配方案的制定更加稳定和高效。

1 干扰效果评估

雷达干扰资源分配过程首先需要对干扰效果进行评估, 然后在评估指标的基础上进行合理的优化分配。

1.1 评估指标

(1) 干扰时机。效益函数Etij代表干扰资源Ji对目标雷达Rj可以有效压制的时段长度对干扰效果的影响大小。定义如下

式中, ωl (l=1, 2, …, k) 是各小段的权重, ωl≥0且

(2) 干扰频率。干扰频率效益函数Efij代表干扰资源Ji对目标雷达Rj的频率的瞄准程度对干扰整体效果产生的影响程度。定义如下

式中, fRj1~fRj2和fJi1~fji2为目标雷达Rj和干扰资源Ji的工作频率范围。

(3) 干扰功率。干扰功率效益函数Epij代表干扰资源Ji对目标雷达Rj的功率压制的程度对干扰的整体效果的影响。定义如下

式中, Pji代表雷达接收机收到的干扰信号的功率;Pjs代表雷达接收机收到的回波信号的功率;Kj代表目标雷达Rj最小的正常工作所需干信比。

(4) 干扰空域。干扰空域效益函数定义为单位时间内的天线波束覆盖的范围Esij= (Ωj+θj) /T, 式中T是干扰天线的旋转周期;Ωj为干扰天线最大指向范围;θj为任意时刻干扰波束范围。

(5) 雷达抗干扰措施。雷达抗干扰措施效益函数定义为式中m为目标雷达使用的抗干扰措施和工作体制的总数, a为目标雷达的抗干扰措施和工作体制先进性的描述因子。

(6) 干扰样式隶属度函数。干扰样式效益函数Emij=N, 其中N为干扰资源所具有的所有干扰样式的数目[4]。

1.2 模糊综合评估

将上述6个指标的效益函数计算结果进行归一化处理后, 可以得到m部干扰资源J1, J2, …, Jm分别对目标雷达Rj实施干扰的指标效益矩阵。根据电子战的实际战情分析配置权重, 以w1, w2, …, w6来表示。则单干扰资源对单目标雷达的干扰效果Eij记为

那么各干扰资源对目标雷达Rj的总体干扰效果的向量为

可以计算得到各干扰资源对各目标雷达的总体干扰效益矩阵[5]

2 动态选择概率的遗传算法

基于介绍的干扰效果模糊综合评估方法, 运用动态选择概率改进的遗传算法搜寻最优解, 可得到基于动态选择概率遗传算法的雷达干扰资源分配方法, 其中动态选择概率遗传算法的主要流程如下:

2.1 编码生成种群

由于染色体的实际意义是雷达干扰资源分配问题的解, 故对染色体采用2进制形式进行编码, 染色体个体记为ak (t) =[x11, x12, …, x1N, x21, x22, …, x2N, xM1, xM2, …, xMN], 其中N为每段染色体的基因位个数, M为染色体段数, 且每个x均在0和1间取值。在整个解空间中随机生成初始种群。图1为M=4, N=3时的染色体种群示意图[6]。

2.2 计算适应度

雷达干扰资源分配方法优劣的评判标准是能够最大限度地利用己方有限干扰资源干扰敌方目标雷达, 那么适应度函数应定义为每个干扰机受到的干扰效益的总和, 定义式如下

式中, E为单个干扰资源对单个目标雷达的干扰效益, 由式 (6) 计算, X为各干扰资源对目标雷达的分配参数, 干扰资源分配给目标雷达X为1, 反之则为0。

分别计算群体中各染色体的适应度, 并引入精英保留机制依照一定的比率保存群体内的最优染色体, 加快收敛速度[7]。

2.3 动态选择概率

由于遗传算法随着迭代代数的增加, 会出现相似染色体浓度不断升高的问题, 从而导致算法陷入早熟收敛, 得到局部最优解。为解决这个问题, 本文采用动态的选择概率的选择操作来替代基本的轮盘选择, 动态选择概率定义如下

式中, P (k) 为各染色体被选择到的概率;k=1, 2, …, Q。Eb和Ew分别为群体内最优与最差的个体经过选择算子操作后的期望, 且有Eb+Ew=2。favg和fmax分别为群体的平均适应度和最优适应度。

经过遗传代数的不断增加, Eb的值在不断改变, 且1≤Eb≤2, 从而对选择概率起到随遗传代数而改变的调整。遗传算法运行初期, 由于初始种群的随机性, 种群平均适应度与最优适应度差距较大, favg/fmax较小, 遗传算法将获得较强的求泛能力, 将优化搜索尽可能延伸至全局空间。遗传算法运行后期, 种群平均适应度与最优适应度越发趋近, favg/fmax趋近于1, Eb趋近于2, 此时遗传算法将获得较强的求精能力, 在局部地区加强搜索。这样的前期求泛后期求精的选择概率可以有效避免早熟收敛, 且保证算法能够快速地收敛至全局最优解。

2.4 种群更新

对父代种群根据竞争择优适者生存的原则按照交叉概率Pc进行交叉操作, 然后根据生物基因变异理论按照变异概率Pm随机翻转某位基因位的2进制基因值。将进行过交叉和变异操作以及未经处理的染色体都放入子代种群, 并引入精英保留机制, 将最优染色体进行存储, 自动进入下代染色体种群。

用染色体适应度和计算时间设置算法的双重终止条件, 若终止条件未满足, 则对染色体群体重复上述步骤, 直到最优个体适应度达到要求或运行时间结束则终止算法迭代, 即可获得基于动态选择概率遗传算法的雷达干扰资源分配方案[8]。

2.5 解码输出最优解

算法终止后, 将种群内染色体进行适应度由大到小的排序, 对适应度最大的染色体个体进行2进制到10进制的解码操作, 每个基因段内的2进制数转为1个10进制数, 则为该基因段对应的目标雷达所分配到的干扰资源序号, 各10进制数将组成1个10进制向量[9]。

根据雷达干扰资源分配问题的实际意义, 该10进制向量即为经过基于动态选择遗传算法的雷达干扰资源分配方法计算得出的最优分配方案。

3 仿真分析

采用Matlab7.1软件对本文所提算法和模型进行了软件的编程实现, 并用仿真实验验证了所提算法和模型以及实现方法的正确性。为了对所提算法进行简单高效且全面的分析, 首先假设战场环境内有8部干扰资源和8部目标雷达, 设置各目标雷达和干扰资源的位置参数、性能参数以及我方干扰资源的重要程度, 并依据上表中的雷达威胁程度权重根据上述介绍的模糊综合评估方法计算雷达干扰效益决策矩阵, 计算结果如图2所示。针对图2中的干扰效益决策矩阵进行干扰分配方案的求解, 为了适应本次仿真环境的实际仿真需要, 设定参数为:种群规模为80, 进化代数为500, 交叉概率为0.7, 变异概率为0.05。则运行结果如图3~图7所示。

观察图3可以看出, 该次运行中动态选择概率遗传算法由于前期采取了求泛运算, 故收敛速度不如经典遗传算法, 但由于其后期的求精运算、干扰效益超越了经典遗传算法, 而经典遗传算法则过早地陷入了早熟收敛, 收敛至了一个局部最优解。观察图6可以看出, 在多次运行的统计结果下, 动态选择概率的遗传算法在收敛速度和最优效益间取得了一个较好的平衡, 对比经典遗传算法来看, 在牺牲收敛速度的情况下取得了更高的最优干扰效益。观察图7可以看出, 动态选择概率的遗传算法在多次运行的统计结果中以较大的概率收敛至更高的最优干扰效益, 可见相比经典遗传算法, 该算法能以更大的概率收敛至全局最优解。从仿真结果可以得出结论:基于动态选择概率遗传算法的雷达干扰资源分配方法由于引入了动态的选择概率, 从而在收敛概率和最优效益间取得了较好的平衡, 预防了经典遗传算法的早熟收敛问题, 使得雷达干扰资源分配方法变得更加稳定和高效。

4 结束语

本文对雷达干扰资源分配方法的理论分析及实现方法进行了研究, 给出了一种基于动态选择概率遗传算法的雷达干扰资源分配方法的理论分析和实现步骤。与基于经典遗传算法的雷达干扰资源分配方法相比, 本文方法对遗传算法中的关键步骤选择操作的选择概率进行了优化, 用前期求泛后期求精的动态选择概率替代了传统的轮盘选择, 从而在算法的收敛速度和干扰效益间取得了更好的平衡, 是一种可以为实际战情双方决策人员提供稳定的雷达干扰资源分配决策方法。并通过建模分析和仿真验证得到了具体的仿真结果, 从而充分验证了本文所提出的方法具有有效性和正确性。

参考文献

[1]吕永胜, 王树宗, 王向伟, 等.基于贴近度的雷达干扰资源分配策略研究[J].系统工程与电子技术, 2005, 27 (11) :1893-1974.

[2]贺静波, 彭复员, 胡生亮.基于作战任务的雷达干扰决策模型[J].现代雷达, 2007, 29 (1) :20-22.

[3]王杰贵, 罗景青.几种雷达干扰资源分配技术[J].航天电子对抗, 2001 (3) :29-32.

[4]任松, 司长哲, 雷军.雷达干扰机分配的模糊多属性动态规划模型[J].系统工程与电子技术, 2008, 30 (10) :1909-1913.

[5]姜宁, 胡维礼, 孙翱.辐射源威胁等级判定的模糊多属性方法[J].兵工学报, 2004, 25 (1) :56-59.

[6]张美恋.资源分配问题的遗传算法[J].集美航海学院学报, 1998, 16 (2) :29-32.

[7]高彬, 吕善伟, 郭庆丰, 等.遗传算法在电子战干扰规划中的应用[J].北京航空航天大学学报, 2006, 32 (8) :934-936.

[8]韩国玺, 何俊, 茆学权, 等.基于改进遗传算法的雷达干扰资源优化分配[J].火力与指挥控制, 2013, 38 (3) :99-102.

[9]张颖, 谭冠政.改进的免疫遗传算法在多机器人协作中的应用[J].计算机测量与控制, 2008, 16 (7) :1001-1023.

动态资源分配算法论文 篇2

关键词：算法设计与分析课程；动态演示；WPF；C#

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）20-0078-02

Abstract： A learning software of algorithm design and analysis course is designed and implemented by using WPF and C# language under the environment of Visual Studio 2010. The bubble sort， the eight queen problem， the tower of Hanoi problem and the knapsack problem are chosen as demonstration of the greedy method， backtracking method， divide and conquer method and dynamic programming， trying to vividly display the demonstration process of above classical algorithms.

Key words： Algorithm design and analysis course； Dynamic demonstration； WPF； C#

算法演示程序是以圖形解释算法，动态演示能够帮助学生加深算法理解，在脑海中形成算法执行过程的直观生动的印象，进而提高算法的教学效果[1]。许多算法演示系统的设计与实现的思想都来源于M.Brown等制作的BLASA系统[2]，随着可视化技术的发展，算法演示程序能够更加生动地展现出求解问题的过程。一个良好的演示系统应当具有丰富的媒体表现力、深入的细节演示效果、灵活的交互能力以及适当的游戏功能四个特性[3]。

1 整体框架

本软件基于微软推出的用户界面框架WPF[4-5]，并在Visual Studio 2010平台下设计与开发的。它提供了可视化界面，用户可直观看到分治法、贪心法、动态规划法和回溯法四种经典算法策略的求解过程[6]，软件的整体框架如图1所示。

2 具体实现

2.1 分治法

本文选择了汉诺塔问题进行分治算法的演示。汉诺塔问题中，每个盘子在柱子上的运作方式与栈结构非常类似：只能移动最上面的盘子。程序中设置了三个栈用于模拟当前三个柱子的状态。

盘子在移动过程中只涉及了四个方向：向上出盘、向左或右边移动、向下入盘。程序设置了一个方向变量direction，出盘过程中，盘子在越过柱子顶部时始终保持了方向direction=0。进程在发现direction为0时会控制盘子一次向上移动一个单位，当盘子的下边界越过了柱子的上边界，direction改变，根据相应信息，将direction设置为向左或者向右方向，左右移动过程以及向下入盘过程的移动方式和判断方法和出盘过程类似，不再赘述。

2.2 贪心法

选取冒泡排序演示贪心算法。我们采用球来表示每一个待排元素[7]，并用其透明度表示元素值的大小。用户输入球体的数目和初试排列状态（程序提供了三种状态：随机排列、逆序排列、正序排列）后，系统内部动态分配等长的球体数组。这些元素都是实例化的对象，能够被添加到画布上。

利用WPF中的Double Animation动画类来实现，它通过指定一个double类型的初始值From和同类型的终值To，使被关联的控件形成动画。如：以下代码可实现Name为lblTest的控件在一秒钟的时间内宽度增加50的动态效果。同样，球体在画布中的位置也是属性，可用动画改变。

一般排序算法都分为两个基本操作：比较和交换。本软件的冒泡排序演示程序就是利用这两个基本操作来进行演示的。如图2所示，若无需交换，则给出提示文字；若需要交换，则利用动画将相应两个球的位置颠倒。

2.3 动态规划法

本文选择0-1背包问题演示动态规划法。具体演示过程：用户完成输入后，点击演示进入演示状态。程序采用单步演示的方式，用户单击按钮，程序演示一步。利用二维数组的列数代表背包的总重量，用户可以修改。程序中使用Grid控件模拟二维数组，Grid内部的Label控件需要动态生成，见如下代码。其中thingCount为物品总数，bagWeight为背包承重，lblC是用于方便访问指定单元格的Label而设置的Label类型数组。

动态规划求中间值的代码如下。其中，第005行的判断表示当前第i个物品的价值与前i-1个物品在背包承重为j-W_arr[i]时的最大价值之和，是否比前i-1个物品在背包承重为j时的最大价值高。

2.4 回溯法

本文选择8皇后问题演示回溯法，图3和4是8皇后问题的相关演示效果图。演示程序中有一个皇后放置的试探过程，如图3所示，黑色棋子表示当前已放好的皇后位置，红色的棋子表示正在试探中。若红色棋子试探成功，则将黑色棋子放在该位置。

在该程序的另一个功能中，用户可以自己放置棋子，来感受8皇后的探索过程。本程序提供了一个错误提示的小功能，若当前棋子与棋盘上某个棋子有冲突，即在同行同列或者同一对角线，那么就会有红线闪烁，表明无法放置，如图4所示。

3 结束语

本软件在设计过程中，参照良好算法演示系统的设计要求，提供了交互功能和图形演示跟踪的功能。在算法的教学过程中能让学生接触直观的操作演示，可更好地让学生知其所以然[8]，也更快地让学生具有利用计算机解决问题的思维方式。不足之处在于它不支持算法跟踪功能，无法从代码上深刻认识算法。

参考文献：

[1]Matthew MacDonald著， 王德才 译. WPF编程宝典——C#2010版[M].

[2]刘铁猛. 深入浅出WPF[M]. 北京： 水利电力出版社， 2010.

[3]陈慧南. 算法设计与分析——C++语言描述[M]. 2版.北京： 电子工业出版社， 2012.

[4]孙永新， 闫大顺. 动画演示与算法教学研究[J]. 现代计算机， 2009（10）： 81-83

[5]张文升， 周青云， 周晓聪. 算法演示系统研究与应用[J]. 计算机应用与软件， 2008， 10：41-43.

[6]李健. 汉诺塔算法演示系统的设计与实现[J]. 现代计算机， 2011（24）： 76-80.

[7]田军， 李丰军. 基于VB程序的冒泡排序算法演示[J]. 电脑知识与技术， 2011（36）： 9410-9412.

动态资源分配算法论文 篇3

关键词：分类挖掘,资源动态分配,模型,算法

对于整个工程项目来说, 资源的合理分配是非常重要的一个环节。传统的分配方法是一种静态分配, 在一些情况下可能会出现因资源分配不合理而引起的严重损失现象。因此, 要想实现工程项目资源的合理分配, 必须在分类挖掘的基础上, 建立动态型的分配模型。在对基于分类挖掘的资源动态分配模型以及基于分类挖掘的资源动态分配算法这两个问题进行分析之前, 我们先来了解一下资源动态分配的必要性。

1 资源动态分配的必要性

从某种程度上来说, 资源动态分配的必要性主要是相对于传统的静态分配无法满足现代社会的需求而言的。传统的静态资源分配, 根本无法根据请求任务的特征及其动态变化来灵活地分配资源, 除此之外, 当有用户的任务请求或者是资源加入与退出现象时, 还无法实现资源分配的自行调节。长此以往, 就比较容易形成资源被长期占用、资源利用效率低下等问题。在这一背景之下, 基于分类挖掘的资源动态分配方法应运而生。它与传统的资源分配方法不同, 可以有效提高资源计算与分配的准确性、合理性等。通常来说, 衡量一种动态资源分配方法的好坏主要有三个指标, 即响应时间、资源利用率以及吞吐量。

2 基于分类挖掘的资源动态分配模型

所谓资源动态分配就是指根据资源池中的资源以及用户请求任务的情况, 对资源分配策略进行及时调整, 以更好地保证资源利用效率的提高。对资源进行动态分配主要是为了解决资源分配过程中所产生的资源碎片问题。一般来说, 基于分类挖掘的资源动态分配模型主要是由用户层、任务调度层以及资源层等几个部分构成的。通常情况下, 用户层是由用户层主要用来向任务调度层中的调度器发送资源请求, 任务调度层包括元调度器和本地调度器两种类型, 其中元调度器的主要职责在于将用户的请求发送至本地调度器中, 而本地调度器的主要职责则在于将用户的各种需求分发到各个集群中去, 以实现对闲置资源的合理配置。由基于分类挖掘的资源动态分布模型可知, 用户一般对资源已经进行了访问, 对各个集群中本地调度器的历史任务信息也已经有了较为详细的记录, 其中CDM代表的是分类数据挖掘, 主要对整个工程项目环境进行挖掘;UM代表的是用户管理, 主要负责对用户进行科学有效的管理;RM代表的是资源管理, 主要负责对资源管理层的所有资源进行管理;RA代表的是资源调度, 主要负责对闲置资源进行合理调度。

3 基于分类挖掘的资源动态分配算法

在探讨基于分类挖掘的资源动态分配算法之前, 我们需要作出如下假设:工程项目中共有n个用户, 分别为u1……un, 每个用户都有w个任务请求, 每个任务请求的时间长度均为T。在分类挖掘的基础上, 我们可以将访问同一集群的用户集合在一起, 并进而得出基于分类挖掘的资源动态分配算法。由以上阐述以及基于分类挖掘的资源动态分配的计算方法可知, 基于分类挖掘的资源动态分配算法将每个集群内的资源进行了合理高效的调度, 具体来说, 它是根据分类原则, 对每个用户的资源访问所集中的时间特征进行了判断, 并由此对请求任务进行了非常直接而又高效的调度。实践证明, 与传统的计算方法相比, 基于分类挖掘的资源动态分配算法可以对处理器资源、存储资源以及宽带资源等多种类型的资源进行协调处理, 以更好地保证这些资源的利用率达到整体的优化与提高, 与此同时对资源分配过程中可能引起的碎片问题进行有效克服与避免。

4 结语

随着我国建筑业的不断发展以及能源资源的日趋紧张, 如何才能在合理分配资源的基础上, 实现建筑工程项目的顺利有序开展, 降低其可能产生的损失就成为人们迫切关注与需要解决的问题。基于分类挖掘的资源动态分配就是一种有效地解决这一问题的方法。可以说, 在未来的发展中, 基于分类挖掘的资源动态分配将会具有非常广泛的应用范围与领域, 可以进行大规模推广应用。本文从资源动态分配的必要性、基于分类挖掘的资源动态分配模型以及基于分类挖掘的资源动态分配算法等几个方面进行了分析与阐述, 希望可以为以后的相关研究与实践提供某些有价值的参考与借鉴。在具体进行阐述的过程中, 可能由于各种各样的原因, 还存在着这样那样的问题, 在以后的研究与实践中要加以规避。

参考文献

[1]张卫红, 刘建民, 张玉洁.多项目施工资源动态分配模型[J].山东建筑大学学报, 2008, 23 (1) :11-14

[2]刘林东.基于分类挖掘的网格资源分配研究[J].计算机应用研究, 2013, 30 (2) :88-89

动态资源分配算法论文 篇4

摘 要：提出了基于遗传算法的面向动态异构多处理器的调度算法（Heterogeneous Scheduling Genetic Algorithm，HSGA），该算法利用连续的多个调度时间片完成遗传算法的迭代计算，在保证计算效率的同时获得较好的调度结果，从而为每个应用选择符合其计算特性的处理器内核.仿真实验表明，本文算法在4核、8核和16核的平台上相比较于经典的匈牙利算法ED2仅分别增加了0.4%，1.1%和1.3%，新的调度算法相比于匈牙利算法和Local调度算法具有更好的调度效果及更好的动态适应性.

关键词：遗传算法；任务调度；功耗控制

中图分类号：TP316.4 文献标识码：A

Abstract：This paper presented an improved scheduling algorithm for dynamic heterogeneous chip multicore processors（Heterogeneous Scheduling Genetic Algorithm，HSGA ）.The proposed scheduling algorithm uses time slices of OS scheduler to complete the iterative procedure of HSGA， which can obtain efficient task scheduling results and choose the best process core for each application task. The experiments using SESC simulator show that the ED2s of the proposed algorithm are only 0.4%， 1.1% and 1.3% higher than those of a baseline classic Hungarian Algorithm with 4 cores， 8 cores and 16 cores chip multiprocessor respectively with random degradation. And the proposed algorithm can generate more stable and adaptive results for unpredictable heterogeneity， compared with Hungarian Algorithm and Local Search Algorithm.

Key words：genetic algorithms；task scheduling；power control

半导体技术的飞速发展使得设计者可以将更多晶体管或者处理器内核集成到一个单芯片上从而构成片上多处理器芯片（Chip Multiprocessor，CMP）.多处理器芯片已经在服务器计算、桌面系统、甚至于嵌入式计算系统中占据了重要的地位，成为目前主流的处理器结构.多核处理器为计算系统带来高性能的同时，也在芯片可靠性方面带来了新的挑战[1-2].

随着片上多处理器芯片的规模逐渐扩大，芯片制造和使用过程中的不可控因素造成的同构处理器性能和关键参数的异构性，成为体系结构和系统层面不可忽视的因素和挑战.就算是在单个晶圆内，由于生产工艺和流程的影响也可能导致各个处理器内核的功耗、最大工作频率等关键参数不同.在这种情况下，原本按照同构片上多处理器设计的CMP芯片可能具有异构性[3-4].大规模同构CMP芯片将面临众多原本应该性能一致的计算内核在功耗和性能方面表现出不一致的情况.如果芯片中某些组件或者电路出现了故障、性能下降与延迟，通过相关技术手段可以使出现性能变化的处理器内核降级使用[5].因此，原本同构的多核片上处理器CMP可能由于多种不可见的因素导致其片上多个处理器内核的性能与原有设计不同.相比原设计指标将存在多个降级使用的处理器内核，此情况称为片上多处理器的动态异构性.

本文主要考虑由于制造过程和使用阶段的不可见因素导致的芯片关键参数变化时多处理器的任务调度问题.对于按同构处理器设计的CMP，若不考虑上述不可见因素带来的异构性而进行任务调度和分配显然难以得到优化的结果.本文提出一种基于遗传算法的动态异构多处理器调度算法（HSGA），在考虑同构CMP处理器出现内核降级使用的情况下，调整任务调度策略，在保证芯片总体功耗满足约束的条件下获得优化的性能.

1 相关研究

已有相关研究考虑同构多处理器降级的问题.文献[4]对CMP处理器的制造过程的可变性对不同处理器内核工作频率的影响进行了评估，他们认为由此带来的工作频率的差异达20%，论文中提出了一系列电路级的方法降低不利影响.文献[6]为了达到CMP芯片功耗控制的目标，将功耗过高的处理器内核关闭.上述工作与本文的目标类似，但他们主要是从电路级考虑和解决动态异构性带来的问题，本文则主要从操作系统的任务调度层面考虑动态异构性给CMP性能带来的影响.

此外，很多工作针对多核处理器上的应用程序的特征进行优化.文献[7-8]主要基于IPC（Instruction Per Clock）统计信息对应用程序行为进行分析从而找到更为有效的任务调度策略.在同构多处理器平台中还使用了任务迁移的技术提高调度效率.文献[9]提出了基于CPI（Clock Per Instruction）栈信息的调度算法.上述工作中对于应用程序行为分析的部分可以作为本文工作的补充，但他们的工作主要基于内核数目少的多处理器芯片，没有考虑同构多处理芯片由于内核数量增加而对任务迁移和系统信息采集方面带来的限制.

多核处理器功耗管理吸引了众多研究者的关注[10-12].Ma等人[10]的工作主要从多处理器芯片全局功耗控制入手，使用自动控制理论对CMP上的处理器内核进行分类，并确定各自的工作频率，所提方法展现了良好的效果和可扩展性.文献[11]与本文工作类似，在考虑制造过程异构性的情况下通过为每个处理器内核设定合理的工作频率来最优化芯片性能.文献[12]考虑了异构多处理器平台上的动态任务调度问题，并给出了MTS启发式方法来解决这个NP难问题.但上述工作的目标平台没有考虑多处理器芯片在使用过程中的故障导致处理器内核降级使用的情况.本文的工作在具备降级使用能力的动态异构多核处理器上，提出基于遗传算法的功耗敏感任务调度算法.

2 系统模型

2.1 系统结构与假设

本文研究的多核处理器CMP指单个芯片上集成了多个同构处理器内核，内核之间通过总线及共享内存进行通信的架构.考虑到制造和使用过程中不可预见的故障对处理器内核性能带来的影响，文中认为部分受影响的内核可以降级使用，即降低部分关键性能参数和指标但仍能正常操作.

本文主要探索在操作系统层面应用自调整的任务调度策略将任务调度到合适的、降级的处理器内核上执行，达到降低动态异构性对多处理器芯片计算性能影响的目的.多处理器任务调度问题是NP难问题，难以在多项式时间内找到最优解.考虑到实际多处理器芯片上优化目标和体系结构细节的复杂性，本文做了一些假设.首先，假设多处理器芯片上运行的任务之间是独立的，忽略任务间通信，并且只考虑单线程执行的情况.这个假设可以使在对任务运行状态采样更为准确的同时不失一般性.其次，假设平均分配外存访问带宽，忽略共享外存带宽占用的情况.简化共享外存的带宽分配策略有助于专注于任务行为特征和调度问题的研究.

2.2 问题的描述

3.2 算法执行框架

1）实现片上多核处理器芯片的全局功耗管理要求芯片内部的各个处理器内核具有实时可调节运行频率的能力.目前AMD公司的Opteron系列多核芯片已具备类似功能，支持芯片全局功耗管理.

2）为了执行片上多核处理器芯片的全局功耗管理的算法，还需要芯片内部具备对每个处理器内核或者分区域内核的实时功耗监测单元.现有Itanium处理器已在芯片内部设置了单独的传感器用于监测各个处理器内核的功耗情况，Itanium处理器独立的功耗管理单元消耗0.5 W左右的功耗，仅占用5%左右的芯片面积[2]，却给处理器的温度和功耗管理带来极大的便利.

3）执行本文算法需要芯片内部设置任务/线程调度器和功耗管理器.这既可由单独的处理器内核负责，也可由操作系统层负责.调度操作与功耗管理操作均由一个较短的采样周期和一个较长的稳定周期组成的时间片内进行.在采样周期中，通过在一小段时间内运行不同的调度方案和功率配置方案，来评估应用程序和异构性能的计算内核的性能和功耗统计信息.上述相关调度决定会在随后的稳定周期中保持，直到下一个时间片.图1为算法执行时间图，假设线程调度时间片为100 ms，功耗管理时间片为10 ms [1-2].

图1中，本文算法在调度采样周期获取处理器功耗开销数据（开销矩阵），获得处理器功耗参数后在功耗采样周期执行所提遗传算法对开销矩阵进行计算，并找到合适的调度方案，找到优化的调度方案后即可在后续的时间片的调度执行周期执行新的调度方案.需要说明的是，本文所考虑的动态异构性对处理器内核性能的影响是偶发的、低频率的事件，因此对在线调度算法的实时性要求不高.利用此特点，将遗传算法较高的计算开销分配到操作系统时间片内多个功耗采样周期中执行，一方面保证了基于遗传算法的调度方案的有效性，另一方面也使得算法的计算开销控制在可以接受的范围之内.

4 实验环境与结果分析

4.1 实验环境

本文使用与文献[2]类似的实验方法和平台.文中主要使用SESC模拟器[1]模拟单个处理器.SESC模拟器可以模拟不同体系结构的CPU，并与能耗模型Wattch，Cacti和Hotspot配合进行功耗与温度调度方面的研究.本文使用的测试集是SPEC CPU2000，并在每个处理器内核上均只执行一个测试程序.为了高效地对不同规模的片上多处理器结构进行模拟，本文使用与文献[2]类似的层次化结构组成多处理器模拟平台.我们构建了一个由多个SESC模拟器构成的多处理器模拟环境来获取各个处理器性能和功耗方面的参数.在此基础之上由一个上层框架负责信息统计、资源管理与调度决策.通过对SESC模拟器的配置可以获得不同性能的、单个的处理器内核.文中假设每个处理器具备相同的、静态分配的外存访问带宽.为了便于实验和比较，选择如表1所示参数的处理器作为基准处理器内核.

使用8个由表1所示主要参数的基准处理器组成标准的8核片上多处理器平台，每个单独的处理器是一个单线程、超标量、乱序执行的兼容MIPS指令集处理器.通过对基准处理器的关键性能进行降级处理来对片上多处理器芯片所面临的动态异构性进行模拟.动态异构性产生的故障可能会对CPU的各个方面带来不同的影响，文献[1-2]对此有较为详细的描述，这里不再详述.本文分别采取4种CPU降级的策略如表2所示.在8核片上多处理器的模拟器中，随机使用下面4种方法对同构处理器内核进行降级处理，从而模拟出具有动态异构特性的8核片上多处理器模拟平台.

为了测试和评估本文所提算法的有效性，通过在SPEC CPU2000测试集中选取不同测试程序组合成不同的负载作为测试输入组合.

4.2 实验结果与讨论

本节对基于遗传算法的动态异构调度算法的实验结果进行分析和讨论.考虑到性能和功耗的平衡，在此选择ED2指标作为主要评价参数[13].所有的测试数据以ED2指标相对于匈牙利算法进行归一化后进行分析.

首先在4核异构多核处理器的环境下对算法的有效性进行评估，为了更好地进行算法实际效果的对比，此处选择以动态异构条件下调度效果较好、但时间成本很高的匈牙利算法[2]作为比较的基础.多处理器线程调度问题可以简化为经典的“指派问题”，匈牙利算法解决此类问题的算法复杂度是O（n3）.Local算法是文献[2]提出的面向动态异构多处理器的高效调度算法.通过对相邻的处理器进行线程“交换”来评估调度效果，若效果好则保留此调度方案，若效果不好则退回原分配方案，迭代进行.

图2为Local调度算法和本文所提遗传调度算法HSGA在4核动态异构多处理器条件下各个负载的ED2值相对于匈牙利算法的逼近程度，其中“误差线”分别表示调度结果中的最好值和最坏值.由图2可知，本文所提遗传算法在5组随机组成的应用负载测试中都表现出比Local算法更好的性能.与匈牙利算法相比，所提遗传算法平均只增加了约0.4%的ED2值.值得注意的是，图2中“误差线”表示了在该组测试集测试过程中所产生的调度方案实际ED2值的动态范围.由于我们从SPEC2000 benchmark测试集中随机选取测试程序组合成多线程测试负载，因此“误差线”在一定程度上反映了调度算法对于不同应用负载在整个测试周期中的动态适应性.所提遗传算法比Local算法表现出了更好的算法阶段行为适应性，也更适用于多核/众核处理器芯片的全局功耗控制调度.

为了进一步验证所提算法的有效性和可扩展性，论文在8核和16核环境下进行扩展实验对比，结果分别如图3和4所示.

图3为8核多处理器上运行SPEC2000 benchmark测试集随机选取的任务负载进行测试的结果.在面临不可预知的动态异构性的情况下，Local算法比匈牙利算法的ED2增加3%左右.本文HSGA遗传算法的ED2仅仅增加了1.1%左右，并依然展现出了较好的动态范围特性.图4为16核多处理器上运行SPEC2000 benchmark测试集的测试结果.处理器数量的增长给动态异构调度效果带来了一定的影响，增加了算法搜索空间.但本文HSGA遗传算法在使用16核多处理器的情况下，整个应用负载ED2值相比较匈牙利算法仅平均增长了1.3%左右，展现了本文算法良好的扩展性.随着处理器数目的增加，传统匈牙利算法的复杂度将变得难以接受.本文算法考虑由于故障或者其他不可预见因素导致的多处理器动态异构性是对不同处理器结构一个偶发的影响，因此将传统遗传算法中较为复杂的算法迭代执行阶段分散到各个调度时间片执行，在不影响应用负载执行效率的情况下获得较好的线程调度效果.

5 结 论

随着单芯片上晶体管密度的不断提升，未来的片上多处理器芯片的规模将会越来越大.制造和使用过程中的不确定因素导致的可变性和故障将使得原本按照同构设计的处理器内核产生不可预见的异构性.与芯片设计时的静态异构性相比，片上多处理器不可预见性的动态异构性对软件系统的设计提出了新的挑战，即使得芯片在具备降级使用的条件时仍能获得可以接受的计算性能.

本文提出了一种基于遗传算法的面向不可预见动态异构性片上多处理器的调度算法HSGA.当片上多处理器由于不可预见的因素导致部分处理器内核的工作频率或者性能出现变化时，本文的遗传算法会在调度时间片内对应用负载特征进行采样，并将传统遗传算法复杂的迭代过程分散到后续多个调度时间片执行，在保证计算效率的情况下提升了调度性能.文中基于SESC模拟器构建了多处理器环境，运行SPEC2000 benchmark进行了仿真实验.实验结果表明，所提遗传算法相比Local调度算法具有更好的调度效果和动态适应特性.下一步，我们将进一步改进算法执行效率，增加算法的可扩展性，并能适应更为复杂的应用负载.

参考文献

[1] TEODORESCU R，TORRELLAS J.Variation-aware application scheduling and power management for chip multiprocessors[C]//Proceedings of the International Symposium on Computer Architecture.Washington DC：IEEE Computer Society，2008：363-374.

[2] WINTER J A，ALBONESI D H.Scheduling algorithms for unpredictably heterogeneous CMP architecture[C]//Proceedings of the International Conference on Dependable System & Networks.Washington DC：IEEE Computer Society， 2008： 42-51.

[3] BORKAR S，KARNIK T，NARENDRA S，et al.Parameter variations and impact on circuits and microarchitecture[C]//Proceedings of the Design Automation Conference.Washington DC：IEEE Computer Society，2003： 338-342.

[4] HUMENAY E，TARJAN D，SKADRON K. The impact of systematic process variations on symmetrical performance in chip multiprocessors[C]//Proceedings of the Conference on Design， Automation and Test in Europe.Washington DC：IEEE Computer Society，2007：1653-1658.

[5] SHIVAKUMAR P，KECKLER S W，MOORE C R，et al.Exploiting microarchitectural redundancy for defect tolerance[C]//Proceedings of the International Conference on Computer Design.Washington DC：IEEE Computer Society， 2003：35-42.

[6] DONALD J，MARTONOSI M.Power efficiency for variation-tolerant multicore processors[C]//Proceedings of the International Symposium on Low Power Electronics and Design.New York：ACM，2006：304-309.

[7] KUMAR R，FARKAS K，JOUPPI N，et al.Single-ISA heterogeneous multi-core architectures：the potential for processor power reduction[C]//Proceedings of IEEE/ACM International Symposium on Microarchitecture.Washington DC：IEEE Computer Society，2003：81-92.

[8] BECCHI M，CROWLEY P. Dynamic thread assignment on heterogeneous multiprocessor architectures[C]//Proceedings of the 3rd Conference on Computing Frontiers.New York：ACM， 2006：29-40.

[9] KOUFATY D，REDDY D，HAHN S.Bias scheduling in heterogeneous multi-core architectures[C]//Proceedings of the 5th European Conference on Computer Systems.New York： ACM，2010：125-138.

[10]MA K，LI X，CHEN M，et al.Scalable power control for many-core architectures running multi-threaded applications[C]//Proceedings of the International Symposium on Computer Architecture.Washington DC：IEEE Computer Society，2011：449-460.

[11]WINTER J，ALBONESI D，SHOEMAKER C.Scalable thread scheduling and global power management for heterogeneous many-core architecture[C]//Proceedings of the International Conference on Parallel Architectures & Compilation Techniques.Washington DC：IEEE Computer Society，2010：29-40.

[12]LIU G，PARK J，MARCULESCU D.Dynamic thread mapping for high-performance， power-efficient heterogeneous many-core systems[C]//Proceedings of the IEEE International Conference on Computer Design.Washington DC：IEEE Computer Society，2013：54-61.

EPON动态带宽分配算法的研究 篇5

关键词：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

动态资源分配算法论文 篇6

基于OFDM的4G无线通信系统LTE[1]的出现引起了无线网络下行链路调度算法设计的研究热潮。在这种系统中,可用的无线下行链路带宽被分为成千上百个并行的正交子频带(子信道),每个子信道可以分配给在基站覆盖范围内的一个用户,一个用户可以同时被多个子信道服务,子信道的分配随着时隙的变化而变化。设计调度的原则就是在给用户分配子信道时必须考虑时变信道的可靠性和用户队列数据的积压,并且保证用户的服务质量。由于无线资源是有限的,而用户的需求相对是无限的,并且由于无线信道的时变性,所以高效的调度算法对于提高系统的吞吐量和用户的稳定性具有重要的作用。

从网络的角度来说,这种系统可以转换为一个多用户多服务器系统[2],每个服务器代表一个子信道。由于在每个时隙一个给定的服务器只能为一个用户服务,因此本文要解决的就是多个用户竞争一个给定的服务器的问题,系统模型如图1所示:

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

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

2 系统模型分析

(1)系统模型描述

系统模型如图1所示,用Q(t)=(Q1(t),...,Qn(t))表示每个队列在时隙t的队列积压(数据包的个数),假设每个队列的缓存区容量无限大,因此没有数据包丢弃。用A(t) =(A1(t),..., An(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成功服务的数据包的个数,则队列的动态更新方程如下:

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

(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信息在每个时隙末会反馈给每个用户队列,已告知传输是否成功,没有传输成功的数据包继续存储在缓存队列中。用示性变量Ii(t)表示队列Qi的传输是否被成功服务,如下所示:

则服务变量表示如下:

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

(3)最优化的目标函数

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

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

其中yi(t)为时隙t中用户i成功服务的数据包的个数。Λ定义为无线网络下行链路的网络容量区,定义为所有可获得吞吐量矩阵 的闭集合。

3 最佳资源分配政策

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

(1)算法设计思想

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

其中βi(t)=1- αi(t),Ti(t)为队列前端的数据包和后继到达的数据包之间的时间间隔。方程(11)可以这样理解:如果αi(t)=0,则βi(t)=1,则队列Qi此时为空,此时仅且当仅有一个数据包到达时Hi(t)=1。相反,如果αi(t)=1,则βi(t)=0,此时有两种情况:1如果队列前端的数据包没有被成功服务(μi(t)=0),则延迟加1;2如果队列前端的数据包被成功服务(μi(t)=1),则下一个数据包到达队列前端,总的等待时间为Hi(t)+1-Ti(t)。由于队列前端数据包和后继到达数据包之间的间隔Ti(t)可能大于或等于Hi(t)+1,在这种情况下,定义t+1时刻队列为空,则此时Hi(t+1)=0。

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

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

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

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

定义每个时隙的漂移-效用函数如下所示:

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

引理1:在每个时隙t,无论 取何值,李雅普诺夫漂移 满足:

式中B是一个有限的常数,将方程(1)和(11)两边平方,并求和,将αi(t)Hi(t)=Hi(t), αi(t)βi(t)=0代入便得到上式,具体证明省略。

引理2:在每个时隙t, 满足:

式中常数B和(15)的一样。本文提出的资源分配算法设计理念就是在每个时隙做控制决定贪婪的最小化式(16)的右边。由于传输决定不会影响Ai( t ) ,则只需使 这一项最大化。

(2)最佳资源分配算法

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

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

其中

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

4算法性能分析

定理1 : 假设存在ε ≥0使 , 令 ,假设 ,则在本文提出的分配算法下有:

如果ε≥0,则所有的队列 的均值稳定。

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

证明:公式(12)可以写为:

(20)式中Wi={1,λi},式(15)可以写为:

对(21)式两边取期望并运用迭代期望定理则有:

两边对τ∈{0,1,...,t-1}求和有:

假设ε> 0 , ( 2 3 ) 两边同时 除以t, 由于 ,则有:

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

由式 ( 2 3 ) 得 :

将式(20)代入式(25),则有:

则对i∈{1,...,n}有:

由于 ,则有:

式(28)两边同时除以t,并在t→∞取极限得:

由式(29)可以看出所有的队列 的均值稳定,(a)证毕。

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

式中 定义见式(10)。

证明:由式(16)得:

将g(y*)=g*和E{μ*(t)}= E{Ai(t)}=y*代入式(31)得到:

对式(32)两边取期望得:

对式(33)两边在τ∈{0,1,...,t-1}求和,并且两边同时除以t得到:

由于L(.)≥0,则有:

对式(35)中的上凸函数g(.)使用詹森不等式[7]有:

对式(36)两边在t→∞取极限得式(30),证毕。

由定理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和图4分别给出了两种算法的吞吐量和延迟的性能。从图3可以看出,在仿真范围内本文所提算法的吞吐量性都能要比随机分配的算法高。图4给出了两种算法的延迟的经验分布,可以看出本文所提算法和随机分配算法相比大大改善了延迟性能。

6 总结

动态资源分配算法论文 篇7

TD-SCDMA系统上下行链路分别在不同的时隙内进行通信以实现时分双工。具有灵活高效的无线传输能力,使得动态信道分配(Dynamic Channel Allocation,DCA)成为不可或缺的一项重要技术[1]。其目的就是尽可能有效地利用有限的信道资源,以提供尽可能多的接入用户,并保证接入链路质量。

根据功能可把DCA划分为慢速DCA和快速DCA。慢速DCA是指把整个网络资源分配给不同的小区,而快速DCA则是把分配给不同小区的资源再分配给小区中的不同用户[2]。但随着用户数的增加,蜂窝小区细分,越区频繁,对用户说来,通话中断率上升比信道阻塞更加严重;同时多数算法只着眼于固定频率,而忽略了其他空余频带资源,对极度紧张的频率资源来说这是相当浪费的,因此这里引入了认知无线电的概念,提出了一种基于可移动边界算法的有效的频带转移算法。

1 边界可移动动态信道分配(MB DCA)

MB DCA是一种可靠的,并且很有效的提高频带利用率的动态信道分配方案。

它的基本思想为:将下行链路4个业务时隙中的2个分配给语音业务,2个分配给数据业务。在业务实施过程中数据业务可借用空闲语音业务信道进行数据传输,语音呼叫到来时,可强占被数据业务借用的信道。语音呼叫到达时,如果语音业务时隙中有2个或2个以上的空闲BRU,就可以进行语音通信,否则该语音呼叫就会发生阻塞;在数据业务借用空闲语音业务信道时,将语音业务信道分成较小的分组。如果语音业务时隙内有零散的BRU空闲,则需要进行信道调整,将这些空闲BRU调整到一个时隙内,然后被借用来进行数据传输[3]。

2 基于认知无线电的MB DCA算法

上述算法的动态资源分配提高了系统利用率,同时也体现了多数动态信道分配算法的局限性——只着眼于固定频段。图2是对Berkeley商业区的0～6 GHz频谱利用率的实际测试。

从图1可以明显地看出在3 GHz以下的某些频段和3～5 GHz之间的大部分频段的频谱利用率很低。在此情况下,可以依靠认知无线电技术配合动态信道分配方案达到提升性能的效果。

认知无线电(Congniteve Radio,CR)能够依靠人工智能的支持,感知无线通信环境,根据一定的学习和决策算法,实时自适应地改变系统工作参数,动态地检测和有效地利用空闲频谱。资源分配模块通过获得的相关参数,动态调整载波、时隙和码道,将业务分配到空闲的频段上去,这样既提高了提高整个频带资源的利用率,又增加了系统业务容量,还减少了系统内系统间干扰[4]。

对于认知无线电采用有中心控制的频谱分配算法,即“只要频谱所有者还有子信道供自己使用,认知用户就可以继续使用频谱的该子信道”的原则[5]。采用“干扰温度”的机制来控制和管理非授权用户对授权用户产生的干扰。系统设定一个保证授权用户正常运行的干扰温度门限,该门限由授权用户能够正常工作的最坏信噪比水平决定[6]。认知无线电在各频段连续不断地检测是否有授权用户在发射信号,若检测到授权用户信号,则认为授权用户存在,非授权用户暂时不使用该频段;反之,非授权用户可以利用该频段传送信息[7]。

在非授权用户获得资源后,对 “干扰温度”使用正常、预警和逃离三级分配方案。具体算法如下:

① 在用户数量少、资源充足的情况下正常使用TD-SCDMA规划的频谱码道等资源。

② 当有新接入用户时,灵活采用边界可移动策略动态接入用户;同时利用认知无线电技术实时感知空闲频率资源。

③ 在MB DCA策略产生一定数量拥塞的情况下,实施频带转移策略。根据认知无线电感知的频率环境情况,以非授权用户的身份向授权用户申请使用该段频率资源。

④ 如果申请成功,则将该频段分配给新增用户。采用相应的载波、码道等分配方案,保证通行质量,同时启用“干扰温度”测量程序。

⑤ 当“干扰温度”处于正常阶段时,新用户可继续使用资源;当“干扰温度”到达“预警”阶段时,用户处于保护状态,RNC进入频带转移策略状态。如果申请到新的频带资源,则重复步骤③,用户进入逃离阶段;若资源申请失败,则产生拥塞。

算法基本流程如图2所示。

该算法改进了MB DCA分配方案,结合认知无线电技术将空闲频率充分利用起来,事实上是现有资源在频率上的搬移,使得系统容量在理论上成倍增加。但是在实际处理过程中会遇到诸多麻烦。比如如何实现空闲资源的准确实时的感知;介于可移动边界分配策略与频带转移策略的分界点在什么情况下有最佳分配效果;干扰温度的选取等等。这些都将影响到该算法的性能,因此需要在实施过程中加以修正。

3 仿真结果分析

为了比较频带转移策略与普通边界可移动分配策略的系统性能,对语音业务阻塞率、数据业务掉包率和系统吞吐量进行计算机仿真。

仿真的假设条件如下:

正常情况下最大可用信道资源为24;

① 语音业务和数据业务的到达量为随机产生,且服从Poisson分布(取整);

② 在仿真MB DCA阶段,如果产生了3个或3个以上的拥塞,则实施频带转移策略;

③ 对“干扰温度”的设置:在授权用户的信噪比(包括非授权用户在内皆视为授权用户的噪声)门限设定为-3 dBm。具体分段设置为:

④ 对于是否有空闲频带资源提供使用:在未知频率状态情况下,非授权用户资源申请是否成功,由随机产生,同时服从二项分布。

在上述假设条件下,编写了仿真代码,经过调试得到一定结果。

仿真结果及对比情况如图3、图4和图5所示。

从仿真结果图可以明显看到,运用新算法以后,在借用到其他频段的情况下,语音业务能够随时接入,使得呼叫阻塞率有明显降低。在语音业务量、数据业务量都较小的情况下语音呼叫阻塞率几乎为0;从数据包掉包率对比图中可以看出掉包率有所减少,且在低业务量的情况下,效果更明显;算法改进后大大提高了系统的平均吞吐量:从300提升到520,提高了将近73.3%,为业务拓展提供了广阔的空间。

4 结束语

经过算法的改进,充分利用了空闲的频带资源,有效地降低了语音业务阻塞率和数据掉包率,很大程度上提升了系统的吞吐量。但是在本算法中未能将认知无线电的干扰温度进行深入的探讨,因此有待进一步研究。

摘要：动态信道分配技术是TD-SCDMA系统的关键技术之一,通过实施动态信道分配方案可以提高频谱利用率、系统容量和提升通信质量。结合现有的可移动边界分配策略,提出了一种基于认知无线电的动态信道分配算法。系统实时感知周围频谱环境,分析并利用空闲频道资源,实现信道的动态分配;最后进行了系统仿真,仿真结果表明改进后系统性能得到一定的提升。

关键词：TD-SCDMA,信道分配,认知无线电,频谱转移

参考文献

[1]李世鹤.TD-SCDMA第三代移动通信系统标准[M].北京:人民邮电出版社,2003:33-39.

[2]蔡晶晶.TD-SCDMA无线资源管理动态信道分配算法研究[D].上海交通学,2006:18-19.

[3]石文孝.基于TD2SCDMA系统的快速动态信道分配方案[D].吉林大学,2007:2-3.

[4]周侨.认知无线电网络中的动态信道分配技术研究[D].浙江大学,2008:17-20.

[5]CAPAR F,MARTOYO I,WEISS T,et al.ComParison ofBand width Utilization for Controlled and UncontrolledChannel Assignment in a Spectrum Pooling System[J].VTC2002,IEEE,2002,92(2):271-294.

[6]PENG M,WANG W.A Novel Dynamic ChannelAllocation Scheme to Support Asymmetrical Services inTDD-CDMA Systems[M].ICCT 2003,Beijing,China,39:20-25.

动态资源分配算法论文 篇8

1 模型假设

假设信道为瑞利信道, 网络中每个节点发送数据的ACK应答都可以被其他节点接收到 (ACK信息的数据量很小, 可以采用冗余更大的信道编码, 增加其抗干扰、衰减的能力, 而增加的开销很小) 。每个接收机可以估计每个链路的信噪比, 而且该信噪比在一个时隙内保持不变。每个节点只有一根天线, 每个节点对收到的数据按最大比合并的方式处理。

2 协作重传的动态TDMA

2.1 数据帧设计

如图1所示, 本文采用了类似文献[8]的帧结构, 整个时隙分为预约和数据传输两个阶段。

数据传输部分为各个节点分配了固定的用于数据传输的时隙。每个节点的时隙又分为本节点的数据发送部分和数据接收节点的应答部分ACK。每个节点在不传输信息时, 侦听其他节点发送的数据是否得到了数据接收节点的应答ACK。如果侦听到ACK, 则认为该节点的数据传输是成功的;否则认为该节点的数据传输是失败的, 需要重新传输。当噪声的功率一定时, 发送失败的数据多是受到了瑞利衰落和通信距离大而导致衰减过大的影响, 因此可以采用协作通信的方式, 降低该影响。预约时隙又分为多个子时隙, 这些子时隙用来交换协作通信所需要的信息, 并动态地分配协作通信的时隙。在动态分配协作通信阶段, 如果某节点没有新数据包产生, 在当前数据帧中该节点相应的时隙时, 协作转发上一帧中其他节点传输失败的数据包, 该策略避免了文献[3]中空闲时隙不足导致传输速率降低的缺点。

2.2 传输失败的计算公式

如图2所示, 假设在第n帧中节点A发送数据包Di给节点C, B, D, E和F为邻居节点。当A向C发送数据Di时, 如果不通过协作直接传输成功, 则认为第一次传输即成功。当第一次没有成功时, 在下一帧中再次传输Di。如果有其他节点愿意帮助A协作重新传输Di, 例如节点B, 则A和B将在各自的数据传输时隙向C传输Di。C在这两个时隙将接收到的Di按最大比合并, 如果译码失败, 则需要在下一时隙继续协作重传。如果Di在需要协作重传时没有其他节点愿意协作传输, 则A单独传输, 如果仍未传输成功, 将继续在下一帧中重新协作或单独传输, 直至成功传输。

当采用BPSK调制时, 节点A发送数据s, 节点C接收的信号可以表示为

则直接传输数据s时, 节点C处的信噪比为

式中:hAC为A和C之间的信道衰减系数, n为高斯白噪声, 满足n~CN (0, N0) 。假设节点之间没有直射波, 所以信道为瑞利信道, hAC~CN (0, kdAC-α) 。k为和信道有关的常数, dAC为A和C之间的距离, α为路径损耗系数。同理, 节点B发送给节点C的信号可以表示为

根据文献[9], 可以得到A和B分别发送的数据在C处按最大比合并 (MRC) 后, 信噪比为

当采用BPSK的调制方式时, 根据文献[9]可以得到A、B组成的天线阵列的平均误码率为

式中:为平均信噪比;m为空间分集数量。如果采用了信道编码, 信道编码的增益为g, 单位是d B, 则采用了信道编码后的平均误码率为

其中

当m=1时, 数据包的长度为N, 当采用了信道编码后, 可以根据式 (5) 计算直接传输, 即第一次传输数据的失败概率为

当m=2时, 表示两个节点协作重传, 一个数据包被协作重传的失败概率为

2.3 协作重新传输策略

如图3所示, 如果A单独发送Di给C失败, 而其没有其他节点正确接收Di, 则A在其下个时隙再次直接重传。如果A单独发送Di给C失败, 并且存在邻居节点B成功接收Di, 则B节点有义务在n+1帧中协作转发Di给C, 前提是在n+1帧的预约阶段B没有本节点的数据需要发送。该协作方式相当于文献[6]中的译码-转发模式。若协作重传不成功, 则A和B在下个时隙中依然协作重传, 直至传输成功才会传输其他数据包。

图4表示的是节点B决定是否协作重传A传输的失败数据包的流程图。假设A节点在第n帧传输数据包Di失败。如图1所示, 预约阶段为每个节点分配了一个子时隙, 如果B在n+1帧的预约阶段没有本节点的数据需要发送, 而且B计算其协作重传的失败率小于A单独重传的一半时, B在其相应的预约子时隙内广播B协作重传A数据包的意愿。A、B节点在第n+1帧中相应的数据传输时隙发送Di。

当B节点子时隙之前的时隙, 已经有其他的节点宣布协作转发Di时, B在本时隙放弃转发Di。如果还有其他节点在第n帧发送数据失败, 例如数据包M, 而且在之前的时隙内没有节点表示愿意协作传输M, B节点会在其第n+1帧的预约阶段子时隙广播协作转发M的意愿。

协作重传的机制可以提高重传成功的概率, 但是为了实现预约协作重传的机制, 在时隙帧的数据传输部分前面增加了预约阶段, 占用了信道资源。每个节点在预约阶段都拥有一个子时隙, 用于广播其协作传输其他节点数据的意愿, 在本文中该子时隙的长度为100 bit。每个数据包的长度为1 024 bit。与图5所示的传统TDMA帧结构相比, CD-TDMA有以下两个特点:

1) 预约阶段占用的时间相当于一个数据子时隙, 对信道的占用降低了数据传输的速率;

2) 提高了重新传输错误数据的概率, 相当于提高了数据传输速率。

CD-TDMA由于比传统的TDMA多了预约阶段, 所以在相同的时间内, CD-TDMA的帧数要比TDMA少, 这意味着数据传输的机会要少。但是, 每个节点在单位时间内产生数据包的概率是相同的, 即在相同时间内产生的数据量基本相同。所以CD-TDMA重新传输数据的机会要比TDMA少, 但是由于CD-TDMA采用协作重传, 重传数据的成功率大大增加, 所以在相同的时间内CD-TDMA传输的数据比传统的TDMA要多。本文第3节将用仿真结果对以上推论进行验证。

3 性能仿真及分析

仿真区域为1 km×1 km的正方形平面, 在该区域内随机分布n个通信节点, 通信速率为200 kbit/s, 仿真时间为10 min。ACK的时间为0.5 ms, 则CD-TDMA和TDM A的数据传输时隙部分, 每个节点被分配了1 kbit/ (200 kbit/s) +0.5 ms=5.5 ms。为了比较CD-TDMA和TDMA的吞吐量性能, 在运行10 min时统计此时各个节点数据缓存区还未发送的数据包之和, 以及在10 min内产生的所有数据包数。未发送的数据包总数与已经产生的所有数据包总数之比可以衡量两种协议的吞吐量性能。当仿真时间达到10 min时, 两种协议产生的数据包总数是基本一致的 (差异小于0.1%) , 此时该比值可以反映两种协议的吞吐量性能。

图6和图7中, δ表示一个节点数据在发送时隙的时间长度内产生数据包的概率, 即在5.5 ms的时间长度内产生一个数据包的概率。由于CD-TDMA和TDMA的仿真时间相同, δ也相同, 所以产生的数据包总量是基本一致的。由图6可以看出, 当δ=0.06时, 无论是CD-TDMA还是TDMA, 因为信噪比增加而导致传输失败的概率降低, 其未发送出的数据包的比例随着信噪比的增加而降低;无论当节点数n=10还是n=15, 未发送数据包的比例基本一致。从图6中还可以看出本文提出的CD-TDMA的性能明显优于传统的TDMA。图7中δ=0.05, 可以得到与图6类似的结论, 证明当δ发生变化时, CD-TDMA协议的性能依然优于传统的TDMA。

图8中描述的是当信噪比为18 d B, 节点数n=10时, 未发送的数据包占总产生数据包比例随δ的变化曲线。从图8可以看出, 随着δ的增加, CD-TDMA和TDMA未发送的数据包显著增加, 这是因为当δ增加时, 产生的数量增加, 未发送的数据比例自然增加。无论δ如何变化, CD-TDMA未发送数据的概率都比传统的TMDA要小, 证明了CD-TDMA协议可以有效地利用协作提高网络的吞吐量。

4 结论

本文提出的动态分配时隙的CD-TDMA算法, 通过协作传输曾经传输失败的数据包, 提高了数据包的传输概率。仿真结果证明了CD-TDMA可以在不同的数据产生速率下, 比传统的TDMA协议有更高的数据传输速率。本文提出的CD-TDMA假设所有的节点都可以直接通信, 在以后的工作中, 需要研究在多跳通信的情况下, CD-TDMA协议的具体性能。

摘要：协作通信可以有效地降低衰落信道中数据传输的中断概率, 从而提高数据的传输速率。但是在TDMA系统中采用协作通信必然引入额外的带宽开销, 为了提高传输速率而采用协作通信, 是否能克服因此而产生的不利因素并不明确。在提出的CD-TDMA时隙算法中, 在传统TDMA帧的前部增加了一个侦听和动态分配时隙的预约阶段。所有节点在每个数据帧的开始如果没有新产生的数据, 则有义务协作转发其他节点在上个时隙帧中发送失败的数据。该算法提高了数据重传的成功概率, 提高了整个网络的吞吐量。仿真结果表明, 尽管该算法引入了额外的时隙开销, 和传统的TDMA接入方式相比, 该算法可以有效地提高整个网络的吞吐量。

关键词：无线网络,时分复用,协作,动态时隙分配

参考文献

[1]LANEMAN J N, WORNELL G W, TSE D N C.Cooperative diversity in wireless networks:efficient protocols and outage behavior[J].IEEE Trans.Information Theory, 2004, 50 (12) :3062-3080.

[2]NOSRATINIA A, HUNTER T E, HEDAYAT A.Cooperative communication in wireless networks[J].IEEE Communication Magazine, 2004, 42 (10) :74-80.

[3]王翠, 唐加山.协作通信技术在恶劣信道条件下的应用研究[J].电视技术, 2013, 37 (13) :101-104.

[4]SADEK A K, LIU K J R, EPHREMIDES A.Collaborative multiple-access protocols for wireless networks[C]//Proc.IEEE ICC’06.Istanbul:IEEE Press, 2006:4495-4500.

[5]JIAO H Z, LI F Y.A mini-slot-based cooperative MAC protocol for wireless mesh networks[C]//Proc.IEEE Global Communicaitons Workshops.Miami:IEEE Press, 2010:89-93.

[6]YANG Zhuo, YAO Yudong, LI Xiaochen, et al.A TDMA-based MAC protocol with cooperative diversity[J].IEEE Comm.Letters, 2010, 14 (6) :542-544.

[7]JIAN Z, KUHN M, WITTNEBEN A, et al.Cooperative transmission schemes for decode-and-forward relaying[C]//Proc.IEEE 18th International Symposium on Personal, Indoor and Mobile radio Communications.Athens:IEEE Press, 2007:1-5.

[8]LEE J K, LEE K M, LIM J S.Distributed dynamic slot assignment scheme for fast broadcast transmission in tactical ad hoc networks[C]//Proc.IEEE MILCOM.Orlando:IEEE Press, 2012:1-6.

寻找课堂的动态资源 篇9

[关键词]资源 动态 兴趣 错误 偶发

[中图分类号] G623.2 [文献标识码] A [文章编号] 1007-9068（2015）16-051

课程资源是指形成课程的要素来源以及实施课程的必要而直接的条件。课堂的动态资源是课程资源的重要组成部分。作为教师，只有准确地寻找到新课改课堂的动态资源并予以开发、利用，才能推进课堂教学向高层次发展，增强教学效果。

一、兴趣

兴趣是一种重要的课程资源。我们认为，课堂就是要使学生能够自然享受学习的过程，让学生从学习新知、动脑思考和想象中体验到学习的趣味。因此，每堂课都要给学生一个舒展兴趣的空间。

如《鸟的天堂》是篇精品散文，深受师生的喜爱，某校一位教师备课时就设想了多种方案，但总是找不到激情。这是为什呢？原来学校所处的福建省漳浦县本身就是全国著名的榕树之乡。学生几乎天天都能见到榕树，几乎对榕树的一切都一清二楚。在这样的情况下，如果按常规进行教学，学生是不会有多大兴趣的。于是，教师决定抛开全部所谓“精品教案”的牵引，另辟蹊径。

师：本地电视节目上说，今天来旅游的客人特别多，他们是来看榕树的。大家高兴吗？

生：当然高兴。

师：但是我们的导游忙不过来呀。旅游公司的同志跟我商量说，要请一些志愿者去帮帮忙。你们谁愿意呢？

（生纷纷争抢这个机会）

师：太好了。可是导游必须能够将榕树的相关知识，以及鸟的生活习性以导游词的形式介绍给大家。因此，我得先考验一下你们行不行。哪位同学先来扮演一下导游接受考验？

学生举起来的小手形成了一片小小的森林

……

学生在轻松的氛围中入境入情，很自然地提出了许多问题。“导游”都能清楚应答，从容对阵，博得了一次次热烈的掌声。这堂课预设的教学目标完满地实现了。

二、错误

一节成功的课往往会因为“错误、发现、探究、收获”的良好循环而充满活力。好的教师应能够及时发现并且善于利用课堂上出现的错误，并以此为契机，引导教学进入有价值的探究领域。如一位教师教学苏教版五年级上册《寻隐者不遇》时，在课的后半部分安排了课堂表演，师生共同扮演诗中的角色。

师：（扮演贾岛，鞠躬施礼）小朋友，你的父亲去哪儿了？

生：（哄堂大笑）不对呀，他不是隐者的儿子！

师：（故作高深）他不是隐者的儿子又是谁呀？

生：是童子。

师：童子是什么角色呀？

生：（怯生生地）是他的学生……

师：那么“隐者”又是干什么的呀？（众生不解）同学们，看来你们对“童子”和“隐者”的意思都还不怎么清楚。请同学们课后自己设法搞清楚这两个词语的意思，下节课告诉老师吧！

这位教师在课中一直回避正面解释“童子”和“隐者”的含义，目的就是为了给学生留下一个独立探究的机会，并以此扩展教学内容。应当说，这一化错误为教学资源的设计是非常巧妙的。

三、偶发事件

课堂中有时会发生教师始料不及的偶发事件，它往往是不可避免的。偶发事件带来的影响有消极的，有积极的，也有双重性质的。课堂出现偶发事件后，教师首先要迅速判断其性质和有无潜在的教学价值。如为消极性的偶发事件，要根据当时的具体情形予以果断处置、平息；如为积极性的或双重性的偶发事件，则要及时转化为新的课程资源，生成新的教学过程。

如作文课上，一条蜈蚣从教室门口窜进教室，爬来爬去。学生们非常害怕，教室里顿时乱成一团。这时有位学生拿出一个塑料袋（农村学生常用塑料袋当书包），张开袋口，放在蜈蚣将要经过的“路口”，待这条蜈蚣钻进袋里，迅速收拢袋口绑紧，再用木棍在袋外将蜈蚣的两颗毒牙折断。险情排除了，教师没有要求学生们回到原来的教学情境中，而是把塑料袋打开，让蜈蚣爬出来（因毒牙已被折断），让学生观察蜈蚣的外形和动作，还让大家回忆刚才蜈蚣爬进来时的情景和那位学生巧捕蜈蚣的情景，最后以《巧捕蜈蚣》为题，让学生把刚才的事写下来，结果学生的作文都写得很好。

教师不失时机地抓住偶发事件，创设新的良好的教学情境，产生了“变废为宝”的效果。

动态的教学资源因其即时性、动态性和隐蔽性，往往不易为教师及时发现和利用。因此，教师应深下工夫，发现、研究动态资源的特点和生成要素，以便用好这份宝贵的资源，提高教学的质量和效益。

动态资源分配算法论文 篇10

农机仿真平台[1,2]主要是为研究农机的工况而搭建的, 在搭建农场虚拟环境时, 由于农场面积广大, 在场景的中的模型众多, 使用Unity3D默认的加载函数会十分缓慢, 进入系统前需要漫长的等待, 所以解决大场景加载缓慢的问题十分必要。本设计采用动态加载算法解决大场景加载问题。

1 算法原理

动态加载的核心思想是异步加载[3], 当用户想加载一个大场景的资源, 不应该从开始让用户长时间等待全部资源的加载完毕。应该优先加载用户附近的场景资源, 需要什么就先加载什么, 在进入平台主界面后, 不影响操作的情况下, 后台加载剩余的资源, 直到所有加载完毕。

异步加载顾名思义就是不影响当前场景的前提下加载新场景。在默认的情况下, Unity3D加载三维场景的时候通常会使用方法Application.Load Level (“Scene Name”) ;此方法主要加载的是在场景中预先存在的所有对象, 即运行程序前该场景中就已经存 在的所有 对象。然 后这些对 象就会在 执行完Application.Load Level (“Scene Name”) 方法后加载至内存当中。

2 算法运行流程

开发人员将三维模型导入Unity3D中, 编辑场景, 完成布局后把每个具体对象 (gameobject) 导出成.unity3d格式的资源文件[4], 并且把整个场景的信息生成一个配置文件, 一般为XML格式。

当平台运行时时, 读取场景配置文件, 根据用户的位置加载附近资源, 先将存储在本地或者网络上的资源文件通过Asset Bundle方法送入 内存 , 若资源文 件较小 , 直接用Asset Bundle.Load () 方法从Asset Bundle的内存镜像里读取并创建一个Asset对象, 创建Asset对象同时也会分配相应内存用于存放, 若文件较大, 则使用Asset Bundle.Load Async () 方法异步加载起源。用户附近的资源加载完毕后开启主界面。在平台运行的过程中, 后台继续加载资源直到所有加载完毕。等到没有任何场景物体在用这些Assets以后, 这些Assets就成为没有引用的数据块, 通过Resources.Unload Unused Assets () 方法来释放资源。

3 算法具体实现

3.1 资源打包

异步加载基于多线程实现, 当场景较大, 同步加载资源耗时较长的情况下, 可以新建一个过渡场景, 将大环境放入过渡场景中, 加载过渡场景, 先将系统界面启动, 与此同时另开线程, 后台加载较为精细的模型对象, 异步加载使用的是API中带的Asset Bundle方法。

异步加载 调用的核 心函数为Application.Load Async (“Scene Name”) 。此方法只能加载Unity3D资源包文件, 打包资源的核心代码如下:

3.2 调用异步方法

按照上述算法将场景资源打包后, 开启新线程, 调用Application.Load Async () 方法异步加载场景资源, 核心代码如下:

4 结语

本文针对搭建农机仿真平台的过程中, 出现资源较多加载缓慢的问题, 给出了使用动态加载算法解决问题的方案, 介绍了算法的原理, 流程和算法的核心代码。使用动态加载算法加载场景中的资源文件, 合理有效, 可以缩短进入系统的等候时间, 提高平台的用户体验满意度。

摘要：在搭建农机仿真平台时, 若虚拟农场里的资源过多, 使用Unity3D软件默认的一次性加载机制会使载入过程十分缓慢, 用户需要漫长的等待时间。针对这个问题, 使用资源动态加载算法优化资源的加载过程, 使平台更加流畅运行。本文主要阐述了动态加载算法的原理和实现过程。

关键词：动态加载,Unity3D,仿真平台

参考文献

[1]谢秋菊, 刘桂阳, 马铁民等.基于Eon的发动机机构运动虚拟仿真研究[J].黑龙江八一农垦大学学报, 2009, 21 (3) :84-86.

[2]李佳, 闫清东, 王一拙.基于ADAMS和Vega的地面机动武器仿真系统的研究[J].计算机仿真, 2006, 23 (2) :236.

[3]Zhu Qunxiong, Jiang Zhiying, Xu Yuan.A Simulation Platform with Real-Time Intervention for Chemical Security Based on Mechanism Model and Virtual Reality Technology[J].Advanced Science Letters, 2012, 11 (1) :498-502.