基于LBT的网格依赖任务调度算法

文章将任务调度分为资源分配和调度执行2个阶段,定义了网格环境下的调度执行最晚开始时间、调度执行开始时间和任务依赖图中边的权值;分析了任务图冻结消减和执行消减对任务图结构的影响;提出了基于LBT的网格依赖任务调度算法;实验表明该算法有效地减弱了网格动态性对调度结果的影响。     

一种基于动态聚合方法的网格任务调度算法

网格中的资源都是动态的,传统的静态任务调度算法不能适应网格的动态特性。通过对资源在未来一段时间内的状态进行预测,可以提高调度算法的性能。文中提出了一种用动态聚合进行调度的算法。首先对处理器的负载进行取样,然后根据网格任务的执行时间,对处理器的取样值进行动态聚合,再利用AR(p)模型进行预测,最后利用预测到的值作为参数对网格任务进行调度,把网格任务分配给每个处理器,使得每个处理器完成子任务的时间都相同,从而使得整个任务的执行时间最短。实验表明,这种算法能很好地适应处理器负载高度变化的情况。     

异构环境下基于任务交互图的调度算法

针对异构环境下任务图为TIG（task interaction graph）的问题，利用松弛标记法善于利用邻居属性处理大量约束的特点，提出一种任务调度算法．算法把任务看作目标对象，处理器单元看作待分配标记，根据对象间所有可能关系，逐渐排除不相关的处理器单元，选择计算和通信综合性能较好的处理器单元．在兼顾任务执行的计算和通信需求的情况下，能够合理分配资源、提高处理速度、缩短整个应用程序的执行时间．实验结果与用穷举法得出的最优结果比较显示，本算法能较理想地解决异构环境下基于任务交互图的调度问题．     

支持资源协同分配的网格任务调度研究

提出通用的网格和任务执行模型,并以此为基础,给出一种支持资源协同分配的任务调度算法。算法通过定义临界资源的概念,改进了传统的列表调度算法。模拟实验结果表明该调度策略更符合网格计算的复杂环境,能得到较短的任务执行时间,并更好的支持不同类型资源的协同分配。     

一种基于任务竞争力的工作流调度算法

网格计算聚集了大量的异构分布式的计算或存储资源,为科学研究提供了一个高性能环境.然而,网格资源的异构性和自治性特征使得任务调度变得极其复杂.针对DAG表示的科学工作流调度问题,根据任务可用资源率确定任务调度的优先级,以任务竞争力刻画任务对资源的最佳匹配度,基于分层调度策略提出了一种基于任务竞争力的工作流调度算法.采用GridSim模拟实验表明该算法相对于其他两个算法,具有更小的执行时间.     

经济网格中基于剪枝策略的时间-费用优化任务调度

由于在经济网格环境下,存在着资源异构和分布的特征,网格任务调度变成了一个复杂的问题.为此,针对独立任务,在考虑用户的服务质量经济需求偏好的基础上,提出了一个优化用户时间和费用的任务调度方案选择算法.该算法首先将网格中兼顾时间和费用的任务调度方案形式化为一个n层m叉树,然后将调度方案的选择问题转化为树的遍历问题,最后利用剪枝方法避免无效路径的搜索,降低了时间复杂度,实现了任务的优化调度.结果表明该算法能按照用户的时限和费用需求偏好选择优化的调度方案,且在性能上优于传统的未剪枝算法.所以该算法是一种可行的任务调度算法.     

改进蛙跳算法的网格任务调度优化模型

为解决当前调度模型存在的局限性, 以更好完成网格环境下的任务调度目标, 结合网格任务调度的NP(Non-deterministic Polynomial)问题特点, 提出了改进蛙跳算法的网格任务调度优化模型。首先以网格任务完成时间作为调度优化指标, 然后采用蛙跳算法找到最优的网格任务调度方案, 并对蛙跳算法存在不足进行改进,以改善算法工作性能, 最后在网格仿真平台GridSim 上进行性能验证分析。实验结果表明, 改进蛙跳算法可较好完成网格任务调度, 缩短了任务完成的时间, 资源负载更加均衡, 而且性能明显要优于其他算法。     

一种面向通信开销的网格工作流调度算法

采用任务—资源分配图定义了网格任务调度模型,运用动态规划的方法提出了面向通信开销的工作流任务调度算法。采用扩展的拓扑排序算法对具有依赖关系的工作流任务进行划分,根据划分的任务子集得到相应的调度阶段,在每一阶段选择满足约束条件和以计算开销、通信开销以及任务执行成功率为最优目标函数的资源节点进行任务分配,从而使工作流任务调度目标函数最优。应用Grid Sim工具包实现了该调度算法,并与Min-Min算法进行对比分析。仿真结果表明,基于动态规划的网格工作流调度算法具有良好的适应性,且能较好地处理不同网络环境下任务间存在大量数据传输的网格调度问题。     

树型网格下独立任务的实用调度算法

讨论在节点计算能力和网络通信速度异构的树型网格下独立任务的调度问题。与最小化任务总执行时间不同（该问题被证明是NP难题[1]）,本文修正[2]中为树型网格平台任务调度问题建立的整数线性规划模型,针对多层树通过线性规划模型求解最优任务分配数的时间复杂性大（ ）的问题,引入推拉方法,将多层树线性规划求解归结为单层树求解,复杂性降低为 ,其中 ,m为树的层数, 为第j层中节点的数目最多的节点的子节点数。基于求出的近似最优任务分配数,提出一个静态分布式的启发式任务调度算法。分析和实验表明,在异构的树型网格下做大量的独立任务调度时,算法性能优于同类算法。 关键词: 任务调度; 网格计算; 线性规划; 最优任务分配; 分布式任务调度算法;     

一种基于任务分解的时间均衡调度算法

网格环境下的任务调度是一个NP完全问题,它一直是网格领域研究的核心。针对计算网格中的任务放牧调度这类问题,提出了一种基于任务分解的时间均衡调度算法。该算法在调度过程中充分考虑了网格资源的特点,采用重复调度和任务分解策略,并进行了仿真实验。在任务完成时间和系统吞吐率两方面与Max-min和Max-int算法进行比较,实验结果证明该算法优于Maxmin和Max-int,是一种性能较好的任务调度算法。     

一种并行的网格资源协同分配方法

针对网格系统中资源协同分配的实时性问题,分析了现有的基于有向无环图的资源映射方法,提出了一种并行资源协同分配算法.该算法采用有向无环图表示每个应用,然后,将所得到的这些图合并成一个有向无环图并对其进行分层,最后,对每层中应用任务的资源分配问题并行处理.分析表明,该并行资源协同分配算法降低了系统中资源调度时间,提高了资源分配的效率,从而能够满足系统实时性要求.     

一种网格计算环境下WDM网路由和波长分配算法

波长路由光网络为网格计算动态提供端到端的专用光路,以满足网格计算应用的数据密集性,提前预留是网格计算中一种重要资源占用形式。目前波长路由光网络的提前预留研究多是关注用户请求的弹性调度,以缓解资源碎片影响。从路由和波长分配(RWA)算法缓解资源碎片影响的角度,分析了提前预留中RWA算法的特殊性,在已有路由和波长分配问题上增加了时间向量因素;并提出了最少资源碎片聚集(L-RFC)算法,引入了时间向量上的资源碎片影响因子作为波长分配权衡因素,将资源碎片影响分散在不同波长上。仿真证明,该算法即降低了阻塞率和资源碎片率,又提高了资源利用率,性能明显优于已有的RWA算法。     

一种网格计算环境下WDM网路由和波长分配算法

波长路由光网络为网格计算动态提供端到端的专用光路，以满足网格计算应用的数据密集性，提前预留是 网格计算中一种重要资源占用形式。目前波长路由光网络的提前预留研究多是关注用户请求的弹性调度，以缓解 资源碎片影响。从路由和波长分配（RWA）算法缓解资源碎片影响的角度，分析了提前预留中RWA算法的特殊 性，在已有路由和波长分配问题上增加了时间向量因素，并提出了最少资源碎片聚集（L-RFC）算法，引入了时间向 量上的资源碎片影响因子作为波长分配权衡因素，将资源碎片影响分散在不同波长上。仿真证明，该算法即降低 了阻塞     

网格工作流中基于优先级的调度方法研究

根据网格用户的身份、信誉，以及网格工作流中应用程序的时间紧迫度和依赖关系，提出了网格工作流中应用程序的优先级计算方法．其中，完全优先级调度算法根据网格工作流中的应用程序优先级向量生成调度序列，而且每次只将队列中优先级最高的应用程序提交给网格，而非完全优先级调度算法可同时调度若干无依赖的网格应用程序进入网格，以弥补完全优先级调度算法的并行化问题．实验表明，当网格中的资源较少且资源的性能差异较大时，使用完全优先级调度算法可以保证优先级较高的工作流的应用程序优先使用优势资源；当网格中的资源性能差异不大时，非完全优先级调度算法可解决因资源未充分利用而造成工作流完成时间大幅增加的问题．     

基于打破对称性的快速寻路算法

基于Java实现了跳点搜索算法,给出了算法实现的过程.实验结果表明:跳点搜索算法找到了一条从起始节点到目标节点的最优路径,且能够有效地识别和消除网格地图上的路径对称性,大幅度减少了节点扩展的数量.对比A*、宽度优先搜索、最佳优先搜索和Dijkstra可知,在所求解的路径长度一致的情况下,跳点搜索在平均搜索时间上显著快于其他算法.因此,跳点搜索是快速、高效的.     

网格中多副本数据的后向预测调度算法

针对网格环境下追求最快响应时间的多副本数据检索应用,提出了一种调度算法,该算法考虑了数据副本分布状况对负载均衡的影响.在被检索数据的多个子集分布在网格中多个节点,并且以数据子集为单位存在不定数目的副本情况下,给出了一种估算存放副本的网格节点动态负载和延时的方法.基于估算出的这些参数,算法根据对响应时间的计算和对后向任务的预测将任务分配到网格节点.后向预测考虑了网格节点被选中访问其上各个副本的可能性.最后通过仿真程序分析了该算法的性能.     

网格环境下一种动态任务调度算法

针对网格系统中资源协同分配的动态性问题，分析了现有的基于有向无环图的资源映射方法，提出了一种动态资源协同分配算法。该算法采用有向无环图表示每个应用，然后，将所有这些图进行分层，执行过程中，就绪的应用组可以按照一定的规则动态插入。该算法解决了网格环境下资源和应用的动态性问题，从而更好的满足了网格的动态特性。     

基于可调节网格改进的跨区域GPSR路由算法

基于定位技术和可调节网格改进现有路由算法, 提出一种基于可调节网格改进的跨区域边界无状态贪婪路由算法, 解决了无线传感器网络边界无状态贪婪路由算法中能量不均衡和高能耗的问题. 该算法利用节点相对位置定位算法\, 可调节网格、 贪婪算法和右手法则建立区域级粗粒度路由路径, 并根据不同区域传感器节点分布的密度, 使用不同方法传输数据. 仿真实验结果表明, 改进算法减少了网络能耗, 延长了网络生命周期.     

Surface Coverage Algorithm in Directional Sensor Networks for Three-Dimensional Complex Terrains

Coverage is an important issue in the area of wireless sensor networks, which reflects the monitoring quality of the sensor networks in scenes. Most sensor coverage research focuses on the ideal two-dimensional(2-D) plane and full three-dimensional(3-D) space. However, in many real-world applications, the target field is a3-D complex surface, which makes conventional methods unsuitable. In this paper, we study the coverage problem in directional sensor networks for complex 3-D terrains, and design a new surface coverage algorithm. Based on a 3-D directional sensing model of nodes, this algorithm employs grid division, simulated annealing, and local optimum ideas to improve the area coverage ratio by optimizing the position coordinates and the deviation angles of the nodes, which results in coverage enhancement for complex 3-D terrains. We also conduct extensive simulations to evaluate the performance of our algorithms.     

基于网格划分的几种空间索引

分析了基本的规则网格空间索引的优缺点,阐述了基于网格划分的各种改进算法的原理,并且针对地图开窗显示的实际应用,设计了每种算法的实现步骤.通过对改进算法时间复杂度和空间复杂度的分析,得出各自的优缺点和适用程度,并根据实际地图数据编程实现这些算法.实验结果表明,在地图开窗显示方面,理论分析符合实际应用情况,每种改进算法时间复杂度都不超过O(N).