【作者】 邢长明；

【导师】 刘方爱；

【作者基本信息】 山东师范大学 ， 管理科学与工程， 2010， 博士

【摘要】 资源共享理论是当前学术界研究的热点问题,随着互连网络技术的发展,网络资源日趋丰富,基于因特网实现这些资源的高效共享在教育、工程技术、社会、医药、经济、管理领域都有着潜在、广泛的应用。例如,在管理领域,资源共享技术可应用于知识获取、广告营销、决策意见形成、组织间信息交换与传播等许多方面。本文从管理科学的角度分析了影响网络资源共享系统性能的四个因素,即资源共享模型、网络拓扑结构、数据存储以及资源调度。在此基础上,选择这四个问题进行重点研究。经过三年的研究,在阅读大量文献的基础上,取得了一定的研究成果。针对资源共享模型,提出了一种层次式的资源共享模型,该模型符合我国教育资源的组织模式,可用于指导教育资源共享系统的建设;针对互连网络,构造了RPC (k)和RPn (k)网络,这两种互连网络具有许多优良的性质,能够提高资源共享系统的通信效率;针对网络演化问题,建立了一种基于Sierpinski分形垫的确定性复杂网络演化模型,该模型在度分布、集聚系数和网络直径等结构特性方面与许多现实网络相符合,可为资源共享网络理论研究提供描述上的借鉴;针对数据存储问题,提出了一种副本创建策略,该策略可以有效解决由于网络节点存储能力较小引起的副本频繁建立与删除问题;针对资源调度问题,提出了基于强化学习的微粒群算法,该算法可以为资源调度决策提供方法支持。经过三年深入的研究,达到了预期的目的,取得了理想的结果,本文的主要研究内容包括以下几个部分:1.提出了一种层次式的资源共享模型,设计了基于该模型的副本创建策略。针对中小学教育资源共享问题,设计了层次式的教育资源网格模型,定义了各层节点的功能;通过与欧洲数据网格对比,分析了教育资源网格的特点;基于层次式的教育资源网格,对影响副本创建策略性能的因素进行分析,然后引入网络带宽和文件大小两个参数,提出了一种动态副本创建策略(EDRS);利用数据网格模拟工具OptorSim构建教育资源网格虚拟环境,分析比较了EDRS策略与Caching-lru策略、Caching-lfu策略和基于经济模型的副本创建策略的性能;最后,综合各项指标分析了不同策略对教育资源网格系统性能的影响。结果表明,EDRS策略在教育资源网格应用中有更好的系统性能。2.构造了一种基于RP (k)的资源共享网络结构,研究了提高系统服务质量的方法和措施。针对分布式资源共享问题,从网络拓扑结构和通信效率两个角度来探讨降低网络延迟时间和提高网络带宽利用率的方法和措施,设计了一种基于RP (k)网络拓扑的资源共享网络体系结构,详细阐述了实现该网络结构连接的方案。在此基础上,给出了提高系统服务质量的策略,包括节点的加入/离开策略、代理策略、分布式资源检索策略以及节点数据的协同策略。最后,通过理论分析比较,证实了采用RP (k)互连网络的优势和相关策略的有效性。3.建立了两种规则的互连网络模型,讨论了其路由算法。Pertersen图由于具有短直径和正则性等特性,在并行计算与分布式计算中具有良好的性能。基于环结构,提出了两种Pertersen图的新扩展方法,构造了互连网络RPC (k)和RPn (k)。研究了这两种互连网络的性质,他们不但具有正则性和良好的可扩展性,还具有比RP (k)互连网络更短的网络直径、更好的可分组性以及更小的网络构造开销。分析了RPC (k)和RPn (k)优于二维Torus以及RP (k)互连网络直径和节点可分组性的条件。设计了RPC (k)和RPn (k)上的单播路由、置换路由、广播路由和多对多路由。研究发现,他们的通信效率比RP (k)网络上对应算法的通信效率均有明显提高。4.构建了一种确定性的复杂网络演化模型,将小世界网络与无尺度网络纳入到一个框架之下。人们发现大量真实网络都表现出小世界和无尺度的特性,例如,面向资源共享的P2P网络,由此复杂网络演化模型成为学术界研究的热点问题。基于Sierpinski分形垫,通过迭代的方式构造了两个确定性增长的复杂网络模型:小世界网络模型(S-DSWN)和无尺度网络模型(S-DSFN),给出了确定性网络模型的迭代生成算法,解析计算了其主要拓扑特性,结果表明两个网络模型在度分布、集聚系数和网络直径等结构特性方面与许多现实网络相符合。最后,提出了一个确定性的统一模型(S-DUM),将S-DSWN与S-DSFN纳入到一个框架之下,该模型不仅可为资源共享网络理论研究提供模型描述上的借鉴,而且可以为复杂网络的相关研究提供理论基础。特别地,我们发现这些网络模型都是极大平面图。5.为了提高资源共享系统决策模块的性能,设计了基于强化学习的微粒群算法。现代优化计算方法可以为许多系统决策模块提供方法支持,为此我们研究了全局优化进化算法:微粒群算法(Particle Swarm Optimization, PSO)。在微粒群算法中,惯性权重作为一个重要参数可以平衡算法全局和局部搜索能力的关系,改善算法的性能。提出了一种基于强化学习的适应性微粒群算法(RPSO),该算法将不同惯性权重调整策略看成粒子的行动集合,通过计算Q函数值,考察粒子多步进化的效果,选择粒子最优进化策略,动态调整惯性权重,增强算法寻找全局最优的能力。对几种经典函数的测试结果表明:RPSO能够获得好的性能,特别是对多峰函数效果更明显。6.设计实现了数据网格任务调度模拟器,为相关策略性能评价提供了一种有效工具。如何评价某一算法的性能,其方法是进行大量的模拟实验。针对数据网格任务调度策略评价问题,归纳定义了数据网格模型及任务调度过程,分析了数据网格的任务执行时间和执行花费,然后基于网格模拟器GridSim,提出了数据网格任务调度模拟器的设计方案,介绍了任务调度模拟器的体系结构、工作流程和关键技术。最后,通过实验表明该任务调度模拟器能很好地满足数据网格优化理论研究的需要,较好地起到帮助寻找最优调度策略的目的。更多还原

【Abstract】 Resource-sharing theory is a hot issue in academic circles currently. With the development of Internet technology and the rich amount of network resources, efficient sharing of these resources based Internet has the potential wide range of applications in education, engineering, social, medical, economic, and management scopes. For example, in management scope, resource sharing technology can be applied to many other aspects such as knowledge acquisition, advertising marketing, decision-making, inter-organizational information exchange and communication. Four factors affecting the performance of network resource sharing systems are analyzed in this thesis, which are resource-sharing model, network topology, data storage and resource scheduling. On this basis, we select the four key issues to study. During the research, much work has been done. For the resource-sharing model, a hierarchical resource-sharing model is presented, which is in line with our organizational model of educational resources and can be used to guide the construction of educational resource sharing systems; for the Internet, RPC(k) and RPn(k) networks are constructed, both of which have many excellent properties and can improve the communication efficiency of resource sharing systems; for the network evolution, a deterministic complex network evolution model was established based on the Sierpinski fractal graph, which has compatible network structural characteristics with a number of practical network on the model degree distribution, clustering coefficient as well as diameter and can be used for the description reference of the research of resource-sharing network theory; for data storage problems, a replica creating strategy is presented, which can effectively solve the frequent replica creation and deletion issues caused by a weak storage ability of network nodes; for the resource scheduling problem, a particle swarm algorithm is proposed based on the reinforcement learning, which can provide method support for the decision-making of resource scheduling.The main achievements of this thesis can be summarized as follows:1. A hierarchical resource-sharing model is presented and the replica creating strategy is designed based on the model. For the resource sharing problem of primary and secondary education, a hierarchical educational resource grid model is proposed, which defines the function of nodes in each layer; by comparison with the European data grid, the characteristics of educational resource grid are analyzed; based on the hierarchical educational resource grid, the factors affecting the performance of replica creating strategies are analyzed, and then two parameters of network bandwidth and file size are introduced, a dynamic replica creating strategy (EDRS) is proposed; using of data grid simulation tool OptorSim to build a virtual environment of the educational resource grid, the performance of EDRS strategy, Caching-lru strategy, Caching-lfu strategy and strategy based on economic models are analyzed and compared; finally, effects of different strategies on grid system performance are analyzed by a comprehensive indicators. The results show that EDRS strategy in educational resource grid has a better system performance.2. Based on the RP(k) network, a resource-sharing network structure is constructed and a series of methods are studied to improve the quality of system services. For the distributed resource sharing issues, ranging from two angles of network topology and communication efficiency to explore methods and measures of reducing the network latency and improving network bandwidth utilization, it designs a structure topology of resource-sharing network system based on RP(k) network, which detailed expound the solution to realize this network structure. On this basis, a series of strategies to improve system quality of services including the node join / leave strategy, agency strategy, distributed resource retrieval strategy, and collaborative strategy for the node data are given. Finally, by theoretical analysis and comparison, the advantages of the RP(k) network and effectiveness of related strategies are confirmed.3. Two kinds of interconnection network model are established and its routing algorithms are discussed. Pertersen diagram has a good performance in parallel computing and distributed computing due to the nature of a short diameter and regularity. Two new extension methods of Pertersen are proposed based on the ring structure, and the RPC(k) and RPn(k) network are constructed. It studies the nature of the two networks, which not only has a regular and good scalability, but also has a smaller network diameter, a better grouped ability as well as a smaller cost of network construction more than the RP(k) network. The conditions of network diameter and grouped ability of RPC(k) and RPn(k) network better than two-dimensional Torus and the RP(k) network are analyzed. Based on the RPC(k) and the RPn(k) network, the routing algorithms are designed, which include point-to-point routing, one-to-all routing, permutation routing, and all-to-all routing. The study finds that their communication efficiency is significantly improved with corresponding algorithms of RP(k) network.4. A deterministic complex network evolution model is constructed, which makes the small-world network and the scale-free network into the same framework. It is discovered that a large number of real networks have shown small-world and scale-free features, such as the P2P resource-sharing networks, thereby complex network evolution model becomes a hot issue in academic circles. Based on the Sierpinski fractal pad, the two deterministic growth complex network model are constructed through the iterative way: small-world network model (S-DSWN), and scale-free network model (S-DSFN). The iterative generation algorithm of deterministic network models is given and their main topological characteristics are analyzed. Results show that the two models are compatible with a number of practical networks on characteristics of degree distribution, clustering coefficient and diameter. Finally, a unified deterministic model (S-DUM) is proposed, which makes the S-DSWN and S-DSFN into a framework. The model not only can be used for the description reference of research on the resource-sharing network theory but also provide a theoretical basis for relevant studies of complex networks. In particular, we find that these network models are Maximal planar graph.5. In order to improve the performance of the decision-making module in resource sharing systems, a particle swarm algorithm based on the reinforcement learning is studied. Modern optimization methods provide support to a number of system decision-making modules, so we study the global optimization evolutionary algorithm: particle swarm optimization (PSO). In the particle swarm algorithm, inertia weight as an important parameter can balance the relationship of the global and local search ability to improve the performance of the algorithm. An adaptive particle swarm optimization (RPSO) based on the reinforcement learning is presented. The algorithm looks different inertia weight adjustment strategies as an action collection of particles, by calculating the Q function values, examines the effect of particle multi-step evolutionary, selects the optimal particle evolutionary strategy, and adjusts the inertia weight dynamic to enhance the capacity of algorithms and find the global optimum. Several test results of classic functions show that: RPSO is able to obtain good performance, especially for multi-peak function.6. A job scheduling simulator of data grid is designed and realized, which provides an effective tool for the performance evaluation of relevant policy. The way to evaluate the performance of an algorithm is a lot of simulation experiments. For the evaluation of job scheduling strategies of data grid, the definition of data grid models and job scheduling process are summarized, the job execution time and costs of data grid are analyzed, and a design scheme of data grid job scheduling simulator is presented based on the simulator GridSim. The architecture, workflow and key technologies of job scheduling simulator are introduced. Finally, experiments show that the job scheduling simulator can satisfy the needs of the grid optimization theory and the purpose of finding optimal scheduling policy.更多还原