【作者】 李志洁；

【导师】 程春田；

【作者基本信息】 大连理工大学 ， 计算机应用技术， 2007， 博士

【摘要】 本文以新的计算基础设施—网格技术为背景，研究如何利用经济学原理来优化网格资源的配置方案。研究目标是解决网格资源分配中的用户出价问题并验证所提方法的有效性。本文从资源分配模型、资源分配算法和模拟实验三个层次上对基于经济模型的网格资源分配进行了研究，内容主要包括并行任务的资源分配、优化用户效用的资源分配、基于负载预测的资源分配以及有限理性下的资源分配，主要研究成果体现为以下几点：(1)提出了一种基于极大熵方法的网格资源分配策略，改善了并行任务的网格资源分配中用户作业的时间优化问题。具有并行任务的多个用户竞争同一资源的时间优化是一个极大极小的难解问题，利用极大熵方法将这个难解的问题转化为一个可微的优化问题，通过二分搜索最优解可得到用户出价的优化方案。讨论了用户出价函数的特征，证明了该方案的存在性和唯一性。结果表明该方案具有较低的时间复杂度，适于优化大粒度的并行网格任务的执行时间。(2)提出了一种基于效用函数优化的分配策略，改善了网格用户需求的异构性问题。利用综合的效用函数来考虑所有网格用户的效用优化，通过柯布-道格拉斯效用函数对网格资源进行合理分配和管理，综合考虑了用户作业执行费用和执行时间两方面的因素，较好的反映了经济模型中各变量之间的权衡，给出了网格用户效用函数的两种可行的优化方案，即基于预算约束的效用优化和基于时限约束的效用优化，并使用拉格朗日方法解决网格用户效用函数的优化问题。结果表明该策略可使网格用户在能估计资源节点拥塞度，并能完成其所有任务的前提下，产生一个合理的出价方案。(3)提出了一种基于序贯博弈的网格资源分配策略，改善了网格资源的负载预测问题。资源负载预测是实现资源优化分配的关键环节，该策略克服了资源的异构性和动态性对判断资源负载状态的不利影响，将正比例资源共享的网格环境中多用户竞争同一计算资源的问题形式化为一个多人序贯博弈，通过寻求该序贯博弈中各个阶段博弈的纳什均衡解，预测资源负载；然后利用此负载信息生成所有用户的最优出价组合和资源的优化价格；最后根据各用户出价按比例分配资源的计算能力，实现了资源的优化分配。结果表明该策略能够得到合理的用户出价，降低资源占用时间，较好地适应了网格环境下异构资源的动态性。(4)提出了一种基于进化博弈的网格资源分配策略，改善了有限理性用户竞争资源的策略均衡问题。该策略运用进化博弈论对用户出价策略的演进进行研究，将网格用户视为有限理性的博弈群，建立了用户出价进化博弈的一般模型。该模型定义了用户出价策略的效用矩阵，然后利用复制动态方程求解网格用户策略选择比例的进化稳定点，并详细讨论了各种用户评估函数对进化稳定点的影响，得到的网格用户出价演化的均衡策略即是进化稳定策略。结果表明进化博弈方法虽然不能直接选择最优策略来实现纳什均衡，但能通过反复博弈，使用户动态地学习并调整自己的策略，克服有限理性的制约，逐步达到稳定均衡，从而实现了网格资源的优化分配。更多还原

【Abstract】 Based on the new computing infrastructure—grid technology, this thesis focuses on how to optimize the grid resource allocation using economic theory. The objective of this research is to solve the problem of grid user bids in grid resource allocation and to test the efficiency of the proposed schemes. The grid resource allocation based on economic model is investigated from two aspects: resource allocation algorithm and simulation. The main contents are the resource allocation for parallel tasks, resource allocation for user utility optimization, resource allocation based on load prediction, and resource allocation under bounded rationality. The primary contributions of this thesis include:(1)Grid resource allocation strategy based on maximum entropy method is proposed to solve the optimal problem of user job execution time in the grid resource allocation for parallel tasks. The time optimization problem of multiple users with parallel tasks competing for a common resource is max-min problem. Maximum entroy method is introduced to convert this hard max-min problem into a differentiable optimal problem. Bisection searching method is used to produce a set of optimal user bids to allocate resource capacity proportionally. Particularly, the characteristics of the user bid function are studied in emphasis and the existence and uniquness of this strategy is proved. The results show that the proposed allocation strategy generates a low time complexity and thus can satisfy the dynamic nature of gird environment.(2)Grid resource allocation strategy based on utility optimization is proposed to solve the problem of heterogeneity of user requirements in grid resource allocation. Take comprehensive utility function into consideration when optimizing all grid user utilities. Cobb-Douglas utilty function is used to configure grid resource because it reflects the tradeoff between various variables of the economic model fairly well. The strategy synthetically considers two factors of execution cost and execution time of user job, and gives two feasible schemes (i.e. utility optimization under budget constraint and utility optimization under deadlines constraint) to optimize grid user utilities. Finally, the Lagrangian method is used to solve the optimal problem of user utility function. The results show that strategy could produce a reasonable bid scheme to guarantee the completion of grid user’s initeraties.(3)Grid resource allocation strategy based on sequential game is proposed to solve the problem of load prediction of grid resource. Resource load prediction is a crucial and difficult problem affecting resource allocation optimization. This strategy overcomes the disadvantages of heterogeneity and dynamic nature of grid resource. The problem of multiple users bidding to compete for a common computational resource is formulated as a multi-player dynamic game. Through finding the Nash equilibrium solution of the multi-player dynamic game, resource load is predicted. Using this load information, a set of user optimal bids is produced to partition resource capacity according to proportional sharing mechanism. The results show that the proposed strategy could generate reasonable user bids, reduce resource processing time, and adapt better to the dynamic nature of heterogeneous resource in grid environment.(4)Grid resource allocation strategy based on evolutionary game is proposed to solve the problem of strategy equilibrium with bounded rational grid users. The strategy using evolutionary game to investigate the evolutionary process of bid strategy of grid user. An evolutionary game model of grid users is established. Using the method of replicated dynamics, an evolutionary stable strategy is produced to allocate resource. Finally, the evolutionary stable point and evaluation functions characteristics of grid users are discussed under different conditions. The results show that evolutionary game approach make grid users study and adjust strategy constantly through repeated games to achieve evolutionary stable equilibrium, which leads to an optimal allocation of grid resource.更多还原