基于多序的空间数据索引结构——MOIS-树

以提高查询效率为目标,运用数据空间分割技术、结合B-树和R-树思想,提出了一种空间数据索引结构——MOIS-树,给出了全新的区域查询处理方法和空间对象按其MBR进行排序的4种序关系定义,并以此为基础给出了MOIS-树的定义,规定MOIS-树中的中间节点的所有孩子节点按其几何位置满足某种序的关系,从而使得在中间节点中进行查询时可以进行快速定位,明显地加快了查询的速度.此外,在查询算法中引入查询窗口包含中间节点MBR的检测,对于较大查询窗口的查询,有效地减少了常规查询算法中大量无效的相交性判断,从另一方面加快了查询速度.给出了MOIS-树的建立算法、节点插入算法及算法的正确性、可终止性证明及时间复杂度分析,并给出区域查询算法及算法的性能分析.实验表明,索引结构区域查询速度有很大的提高.     

基于隐私保护和完整性验证的Top-k查询方法

2层无线传感器网络由于具有寿命长和易扩展的特点,已经成为当前的研究热点.Top-k查询是一种重要的查询类型,但是大多数的Top-k查询不能执行精确查询任务.提出了一种精确的Top-k查询算法PI-TQ(privacy-preserving integrity-verification Top-kquery),同时提供了隐私保护和完整性验证功能.算法采用2次查询方法以减少数据通信量,利用基于干扰数的扰动算法实现隐私保护,并采用概率空间邻居验证模式实现完整性验证.仿真结果表明,PI-TQ算法与同类算法相比较,可以明显减少查询的通信量和计算代价,同时保证查询结果的正确性、隐私性和完整性.     

一种基于对等网络的高效查询机制

如何实现有效查询是对等应用的关键,在分析几种常见的查询算法的基础上,介绍双重指针分布式索引算法的实现过程.通过计算对等网络中文档的流行度和网络的连通状态,确定节点的有用性,进一步决定查询的路由.通过仿真实验,将该算法与几种常用算法在查询耗时、查询请求数量、更新信息数量上进行比较.     

基于概率计算模型改进的相关性层次遮挡裁剪算法

对复杂动态场景进行高效的可见性裁剪是实时绘制领域研究中的一个重要问题.围绕该问题开展工作,并针对相关性遮挡裁剪算法中的问题进行了改进.针对相关性层次遮挡裁剪算法存在冗余和不必要遮挡查询的问题,给出了一种概率计算模型.通过比较遮挡查询时间开销与绘制时间开销的数学期望,改进了相关性遮挡裁剪算法中遮挡查询的查询策略,从而进一步缩小了查询集合,使遮挡查询更加合理.实验结果表明,该算法对深度复杂度高、面片数量大的复杂动态场景有较好的裁剪效率,能够很好地满足实时绘制的要求.     

反向最远邻的有效过滤和查询算法

反向最远邻(RFN)是空间数据库理论与应用中的一类新问题.为了有效地处理数据集中给定点的RFN查询,利用提出的离散边界点及邻域区等概念得到用于判定RFN的候选集的相关性质和定理,并给出其过滤算法.在得到过滤的候选集基础上,提出了F-RFN查询算法.对算法的正确性、可终止性和时间复杂性进行了分析.实验表明采用过滤方式的F-RFN查询比未经过滤的RFN查询的PA效率平均提高约37%.     

传感器网络中基于蚁群算法的实时查询处理

无线传感器网络因不同应用而被广泛部署于各种场合,通常被视为分布式数据库.可以通过向该类数据库发布查询请求来获取事件相关的响应信息.一些具有实时需求的应用对查询时延要求较高,而目前存在的查询算法通常不能很好地满足实时查询应用的需求.针对此类特定应用,提出了基于蚁群优化的实时查询处理算法,该算法采用基于事件重要性的分环存储策略和基于蚁群算法的分布式搜索机制,充分利用蚁群优化算法的自组织和正反馈等特征,综合提高查询处理算法的节能性、实时性及查询请求接受率,为分布式动态并行实时查询应用提供新的思路.执行过程仅需局     

模糊描述逻辑知识库查询蕴涵的判定方法

大规模领域本体的快速发展对语义Web领域的数据访问提出了更高的要求,而基本的本体推理服务已不能满足数据密集型应用中处理复杂查询(主要是合取查询)的迫切需要.为此,大量的研究工作集中在本体和描述逻辑知识库合取查询算法的设计实现上,并开发出了很多知识库存储和查询的实用工具.近来模糊本体和模糊描述逻辑的研究,特别是它们在处理语义Web中模糊信息方面,得到了广泛关注.文中重点研究了模糊SH这一族极富表达能力的描述逻辑知识库的合取查询问题,提出了相应的基于推演表的算法,证明了算法对于f-SHOIQ的真子逻辑的可靠性、完备性和可终止性.证明了算法对于f-SHOIQ是可靠的,并分析了导致算法不可终止的原因.对于该问题的数据复杂度,证明了当查询中不存在传递角色时其严格的CONP上限.对于联合复杂度,汪明了算法关于知识库和查询大小的CO3NEXPTIME时间复杂度上限.     

LBS 中连续查询攻击算法及匿名性度量

k-匿名机制是LBS(location based service)中保证查询隐私性的重要手段.已有文献指出,现有的k-匿名机 制不能有效保护连续性查询的隐私性.提出一种连续查询发送模型,该模型融合了查询发送时间的间隔模型和连续性模型,针对此模型下的两种k-匿名算法Clique Cloaking 和Non-clique Cloaking,分别提出了一种连续查询攻击算 法.在此攻击算法下,匿名集的势不再适合作为查询匿名性的度量,因此提出一种基于熵理论的度量方式AD(anonymity degree).实验结果表明,对连续性很强的查询,攻击算法重识别用户身份的成功率极高;AD 比匿名集的势更能反映查询的匿名性.     

3FO:基于过滤的一种Skyline查询算法

Skyline查询是从一个给定的数据集上返回所有不被其它点支配的点的集合.本文主要针对二维和三维空间上Skyline查询结果的单调性特点提出了一种新的3FO算法,它通过NN过滤、最小值覆盖过滤和单调性过滤三次过滤操作,删除非skyline点数据.可以快速地返回全部的Skyline点.实验结果表明,该算法比传统算法在相同数据集上平均性能提高2-3倍,是一种高效的算法.     

MANET中基于缓存的移动数据查询处理算法的研究

针对MANET环境中带宽有限、能量有限、存储有限和链路频繁的断接性等特点,提出了基于缓存的移动数据查询问题,证明该问题是NP完全问题,并给出一个多项式时间的近似算法,即最大节点新覆盖数据算法MD.该算法采用贪心策略,查询新覆盖数据量最大的节点,减少了查询次数,并最大限度地减少了网络中的传输时延.然后在MD算法的基础上,同时考虑了节点新覆盖数据量和链路服务质量问题,提出了一种改进的高效的启发式算法,即基于最大节点DD值的算法MDD,有效地减少了能量消耗,最小化数据传输时延,提高了网络的吞吐量.理论分析及实验结果表明提出的数据查询算法能够充分利用缓存节点的数据信息,较好地完成数据查询工作,有效地减少数据收集时延,提高查询效率.     

考虑风力发电批特征的电力机组调度问题

电力机组组合问题是在给定的计划周期内确定火电、风电和蓄 电池机组的开关机状态及发电量, 以满足系统的负荷需求、旋转备用等约束要求. 为了降低风电在电网中的供电不稳定 性, 引入蓄电池储能系统与风机进行协调调度. 由于大数量风机的介入, 明显增加了问 题处理的难度和复杂性. 本文从一个新的视角 将相近物理位置的风机进行组批, 基于批的视角对问题建立了批模型. 为 了提高批模型的性能, 提出了批模型参数的变换方法. 根据问题的NP-难特征和模 型的复杂结构, 开发了拉格朗日松弛(Lagrangian relaxation, LR)算法进 行求解. 为了加速算法的求解效率, 提出了子 问题近似求解的代理次梯度的拉格朗日松弛算法. 实验结果表明, 提出的批模型明 显优于传统的单机模型. 基于批模型开发的拉格朗日松弛算法与CPLEX优化软 件相比, 能够在较短的时间内获得高质量的解.     

网格市场中一种模糊决策的多维QoS批调度方法

网格市场环境下,用户的服务质量(QoS)需求更加多样化;更多普通用户加入网格市场,难以提供精确的QoS需求信息.因此,基于用户模糊QoS需求的调度算法成为网格市场中研究的热点.多维QoS网格调度的形式化描述,利用模糊决策理论有效地将用户模糊的QoS需求的映射到网格资源,利用AHP算法确定用户关于多维QoS各维度之间的权重关系,给出一种模糊决策的多维QoS的调度方法.实验表明,模糊决策的多维QoS批调度算法在不需要用户提供精确的QoS参数前提下,有效满足用户QoS需求.与现有的QoS批调度方法相比,该算法具有较好的一次作业完成率,且作业完成率波动较小.     

基于HPC Profile标准的网格批作业服务的研究与实现

以上海超算中心目前急需解决的异构网格中间件之间的互操作问题为研究背景,深入研究了HPCProfile标准及实现的关键技术,设计和实现了基于HPC Profile标准的网格批作业服务,并将此服务集成到各网格中间件上,使之支持多种类型的作业调度器,并在此基础上实现了网格中间件之间的批作业服务互操作,提升现有网格应用系统的可扩展性和网格中间件的互操作性。     

基于混核LSSVM的批特征风功率预测方法

针对风电场风功率预测问题, 利用历史风功率、气象数据和测风塔实时数据等相关信息, 提出了带有批特征的混核最小二乘支持向量机(Hybrid kernel least squares support vector machine, HKLSSVM)方法, 建立风电场风功率预测模型.为了增强模型的适应性, 设计改进的差分进化算法对模型参数进行优化, 并利用稀疏选择方法来选取合适的训练样本集, 缩短建模时间, 保证预测模型精度.根据风场风机的地理位置分布情况, 提出批划分的建模策略, 对相近地理位置的风机进行组批, 替代传统风场风功率预测方法.通过风场中实际数据进行测试, 实验结果表明与其他预测方法相比, 本文提出的方法能够提高预测精度和效率, 减少风电波动性对电网的影响, 从而提高电网的安全性和可靠性.     

一种基于策略的可扩展网格资源管理机制

提出了一种基于策略的网格资源管理机制和采用的关键技术.通过将网格应用的用户和资源节点分别进行分类,较好地处理了网格系统中集中与分布的矛盾.引入资源预留的思想来解决散户的突发批量作业提交.采用集中和分布并重、直接认证和代理认证结合的多策略认证结构,以提高网格安全认证的效率.     

QoS-based Task Group Deployment on Grid by Learning the Performance Data

Overhead of executing fine-grain tasks on computational grids led to task group or batch deployment in which a batch is resized according to the characteristics of the tasks, designated resource, and the interconnecting network. An economic grid demands an application to be processed within the given budget and deadline, referred to as the quality of service (QoS) requirements. In this paper, we increase the task success rate in an economic grid by optimally mapping the tasks to the resources prior to the batch deployment. The task-resource mapping (Advance QoS Planning) is decided based on QoS requirement and by mining the historical performance data of the application tasks using a genetic algorithm. The mapping is then used to assist in creating the task groups. Practical experiments are conducted to validate the proposed method and suggestions are given to implement our method in a cloud environment as well as to process real-time tasks.     

网格计算池模型实现的一些关键技术研究

网格计算池是近年来针对传统“累加”式网格计算模型中网络带宽受限制、通信延迟、通用性不强等缺陷提出的一种新型网格模型。并行计算环境与任务调度管理作为超级计算资源中的重要组成部分,由于其专业性与普及度的影响,长期以来应用的侧重点都更多地在于计算的速度与效率上,在系统开放性上并不注重,对于其二次开发如在网格计算池中的应用更是不多见。就并行计算环境的优化、针对于网格计算池模型应用中的配置和任务调度管理软件以及利用IFL实现网格计算池模型接口中的一些关键问题进行了研究。     

Deadline-sensitive workflow orchestration without explicit resource control

Deadline-sensitive workflows require careful coordination of user constraints with resource availability. Current distributed resource access models provide varying degrees of resource control: from limited or none in grid batch systems to explicit in cloud systems. Additionally applications experience variability due to competing user loads, performance variations, failures, etc. These variations impact the quality of service (QoS) that goes unaccounted for in planning strategies. In this paper we propose Workflow ORchestrator for Distributed Systems (WORDS) architecture based on a least common denominator resource model that abstracts the differences and captures the QoS properties provided by grid and cloud systems. We investigate algorithms for effective orchestration (i.e., resource procurement and task mapping) for deadline-sensitive workflows atop the resource abstraction provided in WORDS. Our evaluation compares orchestration methodologies over TeraGrid and Amazon EC2 systems. Experimental results show that WORDS enables effective orchestration possible at reasonable costs on batch queue grid and cloud systems with or without explicit resource control.     

基于移动代理的网格监控系统设计与实现

网格监控系统对于保障网格系统正常运转极为重要，是近年来网格研究领域的热点之一。以GMA为基础，提出了一种基于移动代理的网格监控架构(MA-GMA)，将基于网格资源有效期的缓存机制与智能性、移动性、自治性等移动代理的特征注入当前的OGSA标准，构造了一个动态的、可扩展的网格监控系统。通过它网格系统的开发者和管理者可以及时发现网格故障根源，分析系统性能瓶颈，为修复和改善系统性能提供依据，使网格系统的服务质量得到可靠保障。     

Adaptive checkpointing strategy to tolerate faults in economy based grid

In this paper, we develop a fault tolerant job scheduling strategy in order to tolerate faults gracefully in an economy based grid environment. We propose a novel adaptive task checkpointing based fault tolerant job scheduling strategy for an economy based grid. The proposed strategy maintains a fault index of grid resources. It dynamically updates the fault index based on successful or unsuccessful completion of an assigned task. Whenever a grid resource broker has tasks to schedule on grid resources, it makes use of the fault index from the fault tolerant schedule manager in addition to using a time optimization heuristic. While scheduling a grid job on a grid resource, the resource broker uses fault index to apply different intensity of task checkpointing (inserting checkpoints in a task at different intervals). To simulate and evaluate the performance of the proposed strategy, this paper enhances the GridSim Toolkit-4.0 to exhibit fault tolerance related behavior. We also compare “checkpointing fault tolerant job scheduling strategy” with the well-known time optimization heuristic in an economy based grid environment. From the measured results, we conclude that even in the presence of faults, the proposed strategy effectively schedules grid jobs tolerating faults gracefully and executes more jobs successfully within the specified deadline and allotted budget. It also improves the overall execution time and minimizes the execution cost of grid jobs.