中南大学硕士学位论文基于市场经济的多目标资源分配方法研究姓名:高明明申请学位级别:硕士专业:计算机软件与理论指导教师:胡志刚20050510基于市场经济的多目标资源分配方法研究作者:高明明学位授予单位:中南大学相似文献(4条)1.学位论文许雷基于非完全信息博弈的网格资源分配策略研究2009网格计算作为一种基于高速网络、面向大区域的高性能并行和分布式计算,将地理上分布的、隶属于不同机构的计算、存储等资源构成一台虚拟的超级巨型机,完成以往单机乃至机群都无法解决的高复杂性计算问题。其中资源管理在网格体系中一直是个复杂而艰巨的问题。本文针对网格环境中资源的动态、异构以及分布的特性,利用微观经济学与统计学中的理论研究了一种优化网格资源分配的新方法。研究目标是提高资源分配效率并验证该方法的正确性。本文从资源分配模型,理论证明,实验模拟三个层面上对该方法进行了分析。具体的研究工作主要分为以下几个方面:br (1)分析了开放式网格体系结构(OpenGridServicesArchitecture,OGSA)和五层沙漏式结构,在此基础上对三种用于网格资源管理的模型(层次模型,抽象所有者模型和市场经济模型)进行对比研究,着重论述了市场经济模型在网格计算环境下公平,高效,便捷等特点。分析了近年来解决市场网格资源分配问题的几种模型,并总结了资源分配领域的几大矛盾问题以及目前解决方法中存在的主要不足。br (2)分析比对多种市场经济网格环境下资源分配模型的基础之上,提出一种“多赢家”式的网格资源拍卖模型(Multi-WinnersAuctionModel,MWAM),即多个用户竞拍一种网格资源。它基于非完全信息博弈理论,通过制定明确的规则,让竞拍者通过价格竞争来确定最终竞拍价,在资源提供者未能给待拍资源定价以及竞拍者彼此独立的情况下公平,灵活地形成竟拍价,即纳什均衡解,并且达到利益的最优化。其快速,公平,可靠的特性以及代价小,便于交易协议的开发等优点非常适合网格环境异构与分布式的特性。br (3)首次将隐马尔科夫预测模型(HiddenMarkovPredictionModel,HMPM)应用到对网格用户出价的预测上。建立了离散时间的HMM模型并对之前t-1个时刻在以每个用户提交的资源需求{r1,r2,…,rt-1}为可观测状态序列条件下本轮分配中用户使用资源的单位出价状态进行预测,从而计算出其能获得所需资源的概率。HMM理论对在网格计算这一高度动态,异构且随机的环境下资源使用者与提供者的行为进行了恰当的数学描述,使得预测结果更加准确,从而提高了资源分配的效率。br (4)从理论上证明了“多赢家”式分配方法的可行性。且可以最大化系统收益。MWAM作为以经济学理论为依托的网格资源分配模型,本文从纳什均衡解的存在性,激励相容性,个人理性,系统收益这几方面分析证明了其适用性与高效性。br (5)通过实验模拟验证了WMAM在网格中的可行性与其自身优势。实验一方面对HMM预测的准确性,以及WMAM在市场网格中的适用性做了纵向分析:另一方面选取序贯博弈资源分配算法,双向拍卖分配算法,基于Qos的资源分配算法,以及“第一价格”拍卖算法,“第二价格”拍卖算法同本文的“多赢家”算法进行横向比较,从不同层面验证了结论。br 通过对理论证明与实验结果的分析可知,本文提出的“多赢家”式资源分配方法满足微观经济学中的激励相容性与个人理性,有较大的准确性与灵活性;同时最优化系统收益,提高资源利用率,增大了交易双方的收益,能更好地适应市场网格环境。2.学位论文李士魁基于市场的网格资源调度和分配研究2009近年来随着网络技术和分布式计算技术的发展,使得将分散的、异构的计算资源有机地整合到一起形成计算网格成为可能。它能跨多个管理域组织或企业进行资源发现、资源管理、信息交换和资源共享。由于网格所具有的广域性、动态性、异构性的特点,网格中资源调度直接影响到整个系统的计算性能,如何对网格资源进行调度和分配以满足用户的需求是一个极具挑战性的问题。br 本文介绍了网格技术的相关概念、特点和体系结构,介绍了网格当中的资源管理,对网格资源特点、组成模块和资源管理中要解决的问题进行了分析,并引入经济学的概念以及经济学在分布式资源管理当中的应用。在上述理论基础上,根据网格资源特征,利用市场经济模型,建立了逆荷兰式拍卖模型,该模型规定了资源的分配策略和初始定价策略。与此同时,本文还在逆荷兰式拍卖的网格资源分配过程中使用了效用函数数学模型,提出了一种新的算法一基于有效的逆荷兰式拍卖算法,该算法在拍卖过程中对网格中的资源动态定价和分配,满足对系统效益的优化。利用GridSim工具箱,实现了基于有效的逆荷兰式拍卖网格资源分配的仿真,验证了该算法的正确性和性能。3.学位论文刘敏网格资源调度与分配的研究2007近年来随着网络技术和分布式计算技术的发展,使得将分散的、异构的计算资源有机地整合到一起形成计算网格成为可能。它能跨多个管理域组织或企业进行资源发现、资源管理、信息交换和资源共享。由于网格所具有的广域性、动态性、异构性的特点,网格中资源调度直接影响到整个系统的计算性能,如何对网格资源进行调度和分配以满足用户的需求是一个极具挑战性的问题。论文首先介绍了网格资源研究的意义、特点和体系结构;然后介绍了网格当中资源的特点、组成模块和对资源管理中要解决的问题进行了分析;并引入了经济学的概念以及经济学在分布式资源管理当中的应用;而后介绍了几种基于市场的网格资源管理模型。在上述理论基础上,根据网格资源特征,利用市场经济模型,建立了逆荷兰式拍卖模型,该模型规定了资源的分配策略和初始定价策略。与此同时,本文还在逆荷兰式拍卖的网格资源分配过程中使用了效用函数数学模型,提出了一种新的算法-基于有效的逆荷兰式拍卖算法,该算法实现了在拍卖过程中对网格资源动态定价和分配,满足对系统效益的优化。利用GridSim工具箱,实现了基于有效的逆荷兰式拍卖网格资源分配的仿真,验证了该算法的正确性和性能。最后,文章对全文的工作进行了总结和分析。4.学位论文王嫚网格环境下资源管理关键技术的研究2006随着计算机性能的不断提高和网络通讯技术的迅猛发展,应用需求日益朝着高性能、大规模、多样性、多功能的方向发展,要求将地理上分布的、异构的各种高性能计算资源、存储资源、数据资源和其它特殊资源通过高速网络连接起来,实现高性能联合计算,共同完成重大应用问题,即广域高性能的元计算技术,也称为网格计算技术[2][3][4]。不同于一般传统的分布式计算,网格计算着重于大规模的资源共享、创新应用,并在一定情况下定位于高性能计算,已经成为一个重要领域。在网格计算环境中,资源是分散在各个不同地域和管理域中,由不同的组织拥有和操作,并且在使用策略和安全机制上各不相同,即不同站点可能会使用不同的局部资源管理系统。同时,很多应用需要同时使用多个站点上的资源,站点自治性和分配资源时可能出现的故障需要一种特殊机制来同时分配位于多个站点上的资源。因此,如何对网格计算环境中的资源进行管理是实现高性能联合计算,共同完成重大应用问题的关键。资源管理是网格计算的核心问题,它包括资源的组织、定位、发现、调度、分配、确认、进程创建以及准备所需资源的其它活动。资源管理提供了管理的功能和概念,使集群能够被当作单一资源,系统管理员根据预先定义好的标准通过资源管理软件确保资源的合理分配和使用,以最终达到资源共享的目的。从为用户提供方便、高效的服务的角度来看,它与传统的分布式计算环境或集群计算环境下的资源管理系统类似,具备以下三种功能:作业管理、任务调度和资源管理,即用户通过作业管理功能向网格系统提交作业,为作业指定所需资源,删除作业并监测作业的运行状态;用户提交的作业由任务调度功能按照作业包含的各个任务的类型、所需资源、可用资源等情况安排运行日程和策略;资源管理功能确定并监测网格资源状况,收集作业运行时资源占用情况等信息。然而,由于网格系统的分布性、异构性和动态性,使得网格资源管理比分布式计算环境或集群计算环境下的资源管理更加复杂,不仅要支持跨组织或管理域的任务调度,实时监控资源和作业执行的状态,而且要维护局部的站点自治,提供相应的QoS支持。因此需要建立适应于网格这种复杂环境的特殊的资源管理系统模型,研究其特征及功能,为具体实现网格资源管理系统提供必要的指导,从而满足网格系统的用户服务需求和为网格系统其它服务组件提供支持。由此可见,在资源管理中,面临的有唯一验证、授权、资源访问、资源发现以及资源调度等挑战。网格中常用的资源包括:处理能力、存储系统、目录、网格资源、分布式文件系统、分布式计算机池、计算机集群等。由于网格在逻辑上连接了属于不同的所有者或组织的多重资源,因而好的资源管理系统在最终网格是否成功上起着重要的作用。但由于缺乏统一的网格资源管理标准,统一的管理协议和原语的对外接口,网格研究仍处于实验阶段,在实现网格资源节点关键功能单元上仍面临着许多困难,尤其是在支持QoS和大规模分布式资源查找方面。为赶上国外的研究步伐,弥补我国在该研究领域的不足,拉近我国与国际水平间的差距,开展网格资源管理及其关键技术的研究已迫在眉睫。本论文旨在对网格资源管理中主要的功能进行前瞻性、探索性的研究,希望能对网格计算的研究工作起到积极有益的指导和推动作用。本论文从理论与实践的结合上,综合论述及分析了国内外网格计算资源管理与调度的发展状况及其技术特征,指出了相关研究工作的局限性。将交叉学科的方法引入本研究中,对网格计算资源管理与调度的若干关键问题进行了研究与探索,试图为网格计算资源管理与调度系统的设计提供一种新的思路和途径。其主要研究工作及贡献可体现在以下几个方面:1、针对网格计算资源管理与调度的特性,将市场经济学模型与网格计算资源管理与调度问题结合起来,基于市场经济模型将经济的概念引入网格资源管理中,既利用了层次模型中相对成熟的技术又明确强调了以市场竞争为基础的资源管理和分配,在市场经济环境中,资源消费者希望最小化费用,而资源所有者希望最大化投资回报。在对已有的基于市场经济的网格资源管理模型作出了一些改进的同时,突出了价格机制在市场中的作用,提出了一种基于市场机制的网格资源分配方法:以均衡理论和第二价格竞拍机制为基础,依靠市场机制,实现计算网格资源的优化分配。首先描述了基于市场的资源分配框架,它包括3个层次:资源层、市场层和消费者层;同时采用第二价格竞拍规则作为资源分配策略,满足了网格对分配系统可扩展性和全局最优调度的需求。与Globus,Legion,WebFlow等计算网格系统中使用的资源分配技术相比,基于市场价格竞拍机制的资源管理模型具有如下的优点:(1)资源分配分层实施,降低了资源分配的执行开销,从而提高了系统的适应性、可延展性(extensibility)和可扩展性(scalability);(2)以经济学中的一般均衡理论为理论基础,遵循第二价格竞拍原理,证明了均衡状态是兼顾效率和公平的资源分配最佳境界,可以使实际的资源分配结果逼近均衡状态,从而使资源分配达到最优;(3)通讯时间及费用少,竞拍效率高。2、网格环境中使用经济学原理进行资源管理和调度是网格从理论研究向实际应用所必须跨越的一步。在计算经济模式下,为调节网格资源供需分配提出了一个基于用户服务需求的计算经济框架。这个框架通过经济学驱动截止期和预算约束根据用户的需求,分配资源到应用任务。提出了一种基于计算经济的网格资源动态调度算法,主要针对网格资源由于计算能力不同而花费代价不同而提出,利用启发式搜索技术,综合考虑了任务的截止期、预算约束、最早可能执行时间等不同因素,通过一个新的资源分配策略实现了时间-代价的最优化,提高了资源调度的成功率。3、针对网格资源动态、分布和异构的特点,需要有一种不依赖集中控制、分布式、可扩展、能适应资源动态变化并且定位性能好的资源查找算法。研究提出了小世界聚类的网格资源查找算法(SWC)算法。将网格空间分为多个簇,按照节点的聚类度确定聚类中心,采用聚类中心优先的分级扩散方法从