【作者】 张燕；

【导师】 贾焰；

【作者基本信息】 国防科学技术大学 ， 计算机科学与技术， 2007， 博士

【摘要】 网格是当前分布式计算研究领域中的热点。如同Web起源于共享物理实验数据的需求那样,网格的研究起源于现代科学探索中对于高性能计算机、大型数据库、昂贵科学仪器灵活共享的要求。网格概念中体现出来的灵活、按需的异构资源集成的思想非常符合人们对更高层次资源共享的需求,因而在分布式超级计算、高吞吐率计算及数据密集型计算等领域得到接受和发展。网格研究的核心是网格资源管理,而网格资源发现则是网格资源管理中的一个基本组成部分,是把资源和资源请求者联系起来的重要环节,是实现网格资源灵活按需调度的重要保障。与传统的分布式系统相比,网格中集成的资源规模更大、种类更丰富,且分属于不同组织,参与网格的各个节点往往拥有不同的利益和资源管理策略。因此良好的可扩展性、分布性、自适应性等特点是大规模网格资源管理对资源发现技术的必然要求。然而,目前网格系统中的资源发现机制基本上仍是集中式的,尽管这种方式实现简单,但是随着网格规模的增大、网格资源种类及数量的增加,集中式的资源发现方式逐渐成为性能瓶颈,出现了可扩展性差的不足。因此,网格资源发现方法面临着新的挑战。另外,随着开放网格服务体系结构OGSA(Open Grid Service Architecture)的提出,网格中的资源以服务的形式呈现给用户,网格资源发现的过程体现为网格服务的发现过程。现有的基于关键字的网格服务发现方式存在灵活性差、查全率和查准率低等缺点,在此基础上改进的基于语义的网格服务发现方式虽然在灵活性及查全率和查准率等方面得到了提高,但是存在服务发现时间耗费大的问题。针对上述现有网格资源发现技术的不足,本文致力于解决集中式资源发现技术无法适应网格规模的增长、可扩展性差及传统网格服务发现技术查全率和查准率不高、服务发现时间耗费大等问题,主要创新工作包括:(1)在提高网格资源发现技术的查找效率及成功率等性能指标方面,提出了一种基于自适应k近邻聚类的网格资源发现方法。该方法使用了一种两层层叠网络来表示网格资源节点间的逻辑关系,其基本思想是采用自适应k近邻聚类算法对具有相似特征的资源进行聚类,并建立相应的类间消息转发机制,以此缩减资源发现的搜索规模和资源信息更新的扩散范围,从而提高资源发现性能。同时,我们还构造了一个用于研究网格资源发现方法性能的网格仿真环境,设计并实现了相应的仿真引擎,利用仿真对本文所提出的基于自适应k近邻聚类的网格资源发现方法和现有的其它网格资源发现方法进行了定量比较。仿真结果表明,本文所提出的网格资源发现方法具有较好的资源发现性能,能适应网格规模变化的需要,具有较高的资源发现效率和较好的自适应性。(2)在增强网格资源发现技术的可扩展性方面,提出了一种基于P2P方法的网格资源发现方法。为了适应网格系统的规模变化及资源动态性的特点,实现高效非集中式的网格资源发现,本文将P2P方法应用到网格资源发现领域,提出了一种基于P2P方法的网格资源发现方法。该方法使用二叉树来管理资源信息,网格中的每个节点都可以充当资源信息节点,都负责管理一部分资源信息,同时它还维护一张路由表,以便将资源请求转发给相应的邻居节点。在此基础上,本文还给出了网格资源信息的分配算法及资源信息更新算法,并对资源信息更新算法所产生的消息开销进行了研究;针对用户的资源请求,提出了一种与之相适应的区间查询算法,并对该算法进行了分析。实验结果表明该资源发现方法既能避免集中式资源发现机制中资源信息服务器负载过重,容易造成单点失效的问题,又具有良好的可扩展性。(3)在提高服务发现的查全率和查准率及满足用户对服务请求的实时性要求方面,提出了一种基于本体的网格服务匹配方法。针对传统的基于关键字匹配的网格服务发现方法存在灵活性差、查全率低等缺点及现有的基于语义的服务匹配方法耗时高的不足,本文提出了一种基于本体的网格服务发现方法。该方法使用本体描述语言OWL-S来描述网格服务,体现了网格服务的语义信息。在服务匹配之前,该方法利用描述逻辑推理机自动对网格服务本体中的概念和已经发布的网格服务进行分层预处理,并采用有向无环图来表示概念间和服务间的层次关系。对于用户提交的服务请求,在有向图上进行服务匹配比直接利用逻辑推理机进行服务匹配更为高效,能很好的满足用户对服务请求的实时性要求。实验结果表明,该方法在查全率和查准率等性能评价指标上比基于关键字匹配和其它基于语义的匹配方法要高;与直接基于OWL推理机的服务匹配方法相比,该方法以服务发布阶段构造概念分层和服务分层的时间开销为代价,换取了服务查找阶段用户请求响应时间的大幅度提高,更能满足用户对服务请求的实时性要求。更多还原

【Abstract】 Grid is a hot topic in distributed computing nowadays. Just like Web, which is developed to meet the requirement of sharing scientific experimental datum at the beginning, Grid concept is motivated by the needs to share high-performance computer, large database and expensive instrument in modern scientificre research. The real and specific problems that underly the Grid concept are coordinated resource sharing and problem solving in dynamic, multi-institutional virtual organizations. Since 1990s, considerable progress has been made on the construction of such an infrastructure, more over the Grid concept has been widely accepted and refined in many fields such as distributed supercomputing, high-throughput computing and data-intensive computing since then.Resource discovery is a basic element in Grid resource management, which concerns discovering resources in Grid to meet the requirement of applications. Compared with traditional distributed systems, Grid aims to integrate much more resources of diverse varieties belonging to different organizations. In addition, providers and consumers of Grid resources usually have different or even contradictory interests. With further development of Grid, centralized Grid resource discovery schemes give birth to potential scalability problems. Therefore, in order to survive the dynamic and larger-scale Grid environment, resource discovery should be decentralized and should not rely on centralized coordination and control.In addition, with the advancement of the concept of OGSA, resources in Grid are presented to users by the form of services. Therefore, Grid resource discovery show itself as Grid services discovery. The existing keyword-based Grid service discovery methods have some shortages, such as poor flexibility, low precision and low recall. Although the improved methods make some progress in the aspects of flexibility, precision and recall, it still has high time cost on service discovery.Focusing on scalable and efficient decentralized resource discovery in Grid environment, this paper makes following contributions:1. Proposes a novel grid resource discovery method based on adaptive k-Nearest Neighbors clustering, which improves the resource query efficiency and succeed rate.This method uses a two-layer overlay to describe the logical relations between resource nodes. In our method, a class is formed by a collection of nodes with some similarities in their characteristics. Each class is managed by a leader and consists of members that serve as workers. At the same time, to reduce the resource search scope and the propagation scope when updating resource information, we propose a corresponding efficient requests dispatch mechanism. A simulation environment is constructed to study Grid resource discovey performance, and a simulation engine is also implemented. The experimental results show that our method achieves better scalability and efficient lookup performance.2. Proposes a P2P-based Grid resource discovery method with well scalablity.In order to suit the development of the Grid scale and resource dynamics, the P2P method is adopted, and a decentralized resource discovery method with well scalability is presented. This method uses binary tree to manage data, each node in Grid is responsible for managing a part of resource information. It maintains a routing table to guarantee that the search can start at any node as well. At the same time, an algorithm for Grid resource information manangemt is presented, and the message cost of resource information update is also analyzed. For users’ resource request, a range query algorithm is proposed and analyzed. The experimental results show that this method resolves many problems that exist in centralized mechanism, such as poor scalability, heavy load on resource information server and single point failure.3. Proposes an ontology-based Grid service discovery method, which improves precison and recall, and reduce the responding time of users’ request.To improve the efficiency of Grid service matching, a novel Grid service matching method based on ontology is presented. This method uses OWL-S to describe Grid service, which takes into account the service semantic information. Before matching Grid services, DL-reasoner is used to form concept hierarchy and service hierarchy. The experimental results show that compared with exsiting keyword-based methods and semantic methods, our method has better recall and precision. When compared with the methods based on reasoner directly, although our method has some shortages of time cost for constructing concept hierarchy and service hierarchy, the users’ request responding time is notably reduced. Consequently, our method can better meet the needs of users.更多还原