摘要网格资源分配研究中，结合成熟的经济学模型成了非常重要的研究方向，而在各种经济学模型中，组合双向拍卖模型由于其非常适用于网格环境大规模、异构、动态等特点，现已经成为网格资源分配的研究重点，但是仍旧存在着诸多问题，如组合双向拍卖中节点或实体在单次拍卖中分别扮演资源提供者和资源需求者中单一角色；实验分析给出的买方和卖方数基本都是对等或接近的等问题。信任机制同样也是网格资源分配的研究重点。它提供了一个适合网格应用的开放、分布和动态特性的安全决策框架。信任模型能够对网格中实体信任度进行描述并且能够在网格实体间建立信任关系，使得网格系统变得更加健壮、安全；信任模型中的惩戒机制可以对网格中的恶意节点进行惩罚，使其失去一定的网格权限直至驱逐出网格，使得网格系统变得更加可靠。
关键词：网格；资源分配；信任度；混合组合；组合双
第1章 绪 论
1.1 研究背景及意义
网格研究的奠基人Ian Foster和Carl Kesselman在1998年的文献中首次对网格进行了定义[1]：“计算网格是一个包含硬件和软件的基础设施，它能对高端计算能力提供可靠的、一致的、普遍的和不昂贵的接入。”2000年，Ian Foster等人在文章中进一步将网格描述为[2]“在动态的多机构的虚拟组织中协调资源共享和协同解决问题。”这个定义提出了虚拟组织、资源共享和资源协同的思想，细化并发展了前面的定义。2002年Ian Foster提出了网格的三个判断标准，即协调非集中控制的资源，使用标准、开放和通用的协议和接口，以及提供非平凡的服务。不断增长的Internet使用也造成了成本的增加。基于宽带的高速应用的实现和维护需要有更多的成本；激励机制、拥塞控制和流量控制等控制手段都会造成网络运营成本的增加。目前的Internet发展成为遍布全球的服务网络，不同的Internet应用属于不同的服务供应商，这又对价格体系提出了更高的要求。另一方面，新的网络发展背景为网络资源优化分配问题研究赋予了新的内涵[3]。资源使用率己不再是资源分配唯一的优化目标，用户满意度、系统效率等要素在优化分配过程中必须考虑[4]。 因此，有必要研究并采取一种更合理的价格机制和体系，体现资源价值，收回成本为网络市场运作提供基础。面对这些问题，我们有必要研究一种新网络服务定价模式，它不仅要合有效地分配资源，还要支持多级别的服务模式，不仅要能够从用户那里收回网络服务运营成本，还要能够提供高质量的网络服务[5][6]。
网格技术诞生于上个世纪90年代中期，其思想来源于电力网格。在人们通过开关打开电灯时，通常并不需要考虑这种可以照亮房间的能量是从何而来的。我们无需关心能量是否来自于水电、火电、还是核电，或者是否来自于风、太阳能之类的替代能源，也不需要考虑这些电站位于何处。因为它们构成了电力网格，对于电力网格中大量不同的应用，他们均具有连接到电力网格的简单的接口，通常是通过一个电插座就可以直接达到获取电能的目的。另外，电力网格中的能量是作为商品进行交易的，且其价格是随着供求关系的变化而波动的[8]。
上面的描述就是我们计算机网格的原始思想，我们可以设想一个以同样简单的方式获取计算能力的场景。在这个场景中，计算任务将在其所需的最合适的资源上运行，其中数字密集型任务可以在远程的超级计算机上运行，而需求较低的任务可以在稍小的本地计算机上运行。调度器用来将计算任务分配给计算资源，且这个过程对于终端用户是隐藏的。这种透明地接入到远程分布式计算资源的方式与许多用户使用计算机的方式很好的吻合，通常情况下，用户并不关心其计算作业是在何处完成的，只要能够确保其作业的运行以及将结果快速的返回给用户即可。透明性也适用于数据存储的应用，用户无需知道他们所访问的数据的地理位置。这种透明性与电力网格中用户无需关心电能是如何以及在何处产生是类似的。此外，在这个场景中，可以通过不同的平台，包括台式机、笔记本以及各种可连接到网络的移动设备等，来快速地访问远程计算资源。这种方式称为普遍接入。在电力网格中，普遍接入的特性是从通过标准的壁上插座对电能的普遍获取来表现出来的[8-9]。
1.2 国内外研究现状
现有的网格资源分配的经济模型主要包括基于价格的理论和基于博弈论的理论[7]。基于价格理论的基本思想是：通过价格杠杆进行调节在供给大于需求时价格下调，刺激消费；在供给小于需求时价格上调，抑制消费，直到达到系统总需求等于系统总供给的均衡状态。基于博弈论理论的思想通常采用拍卖与投标的方式进行市场调节，最终获得Nash均衡达到系统总效用的最大化。当前各种经济模型的研究基本上都是建立在以上两种理论的基础上。能用于网格资源分配的经济模型主要包括以下几个：(1)市场模型(Commodity Market Model)。这是最简单的一种市场模型，其中资源的所有者指定其提供网格服务的单位价格并根据用户对资源的消费量向用户收取费用。根据资源的供需关系对价格影响程度的不同可以分为稳定价格和供需驱动价格两种。(2)标价模型(Posted Price Model)。标价模型与商品市场模型类似，区别在于，资源所有者标出其特色服务功能，或者价格优惠的资源使用条件，从而吸引新的用户，占领市场份额，以及激励用户在价格优惠的时段使用网格资源。(3)议价模型(Bargaining Model)。在前两种市场模型中，交易价格是由资源所有者首先提出的，资源使用者采取接受或不接受的方式，而在议价模型中，用户可以通过向GSP提出更低的交易价格或者要求更多的资源使用时间等方式来实现价格协商。(4)招投标合同网模型(Tender Contract-Net Model)。招投标合同网模型是基于商业贸易中用来控制商品或服务交换的契约机制。(5)拍卖模型(Auction Model)。拍卖模型作为市场价格机制的重要补充，具有其他买卖形式不可替代的功能，除了揭示信息、发现价格这一基本功能外，还具有减少代理成本、稳定市场价格、加速商品流转等功能。另外，还有基于投标的按比例资源共享模型(Bid-based Proportional Resource sharing Model)，垄断寡头市场模型(Monopoly Oligopoly Model)[9][10]。定价方法就是要基于上面各种经济模型，制定定价机制，现阶段定价机制研究主要有自治定价机制[11]、基于博弈论的移动网格定价[12]、基于商品市场以及负载预测理论的定价[13]、基于双向拍卖的定价[14],以及基于组合双向拍卖的定价[15][16]。
网格经济的另一个重要的研究方向是信任机制[17]，涉及到网格安全与服务质量两方面。基于信任度对恶意节点进行鉴别，有效加强了网格资源分配的安全性。以信任度作为服务质量的反映，提出基于信任度的资源分配策略，可确保高信任度节点有更大收益，有效激励节点提高服务质量。1996年，M Blaze等人将人类社会学中的信任关系引入到计算机网格系统中，提出了信任管理(Trust Management)的概念[18]，并且在此基础上提出了相应的信任管理系统PolicyMaker。文中认为网格中安全信息是不完整的，系统的安全决策需要依靠可信任的第三方提供附加的安全信息。同时提出信任管理是网格服务安全一个独特而重要的组件，信任管理提供了一个适合网格应用的开放、分布和动态特性的安全决策框架。在网格环境下研究信任模型具有重要的作用和深远的意义，主要体现在：相对传统的安全机制，信任模型能够对网格中的实体信任度进行描述并且能够在网格实体之间建立信任关系，使得网格系统变得更加健壮、安全；信任模型中的惩戒机制可以对网格中的恶意实体进行惩罚，使其失去一定的网格权限直至驱逐出网格，使得整个网格系统变得更加可靠。现阶段网格环境下信任模型的研究已经开展的相当顺利，出现了基于奖惩机制的信任模型[19]，基于多维度的信任模型[24][25][26]，基于近期表现或时间自衰减等信任模型[20][21]等等。
定价和信任在当前的网格经济模型中大多处于分离状态。网格定价机制能够调节资源供需平衡，解决资源效用最大化和拥塞控制等问题，但是网格环境的异构性、动态性和多管理域等特点，给网格资源分配的研究带来了很多全新的挑战。网格安全基础设施(GSI)解决了网格环境下的安全认证和安全通信问题，但无法处理网格市场中节点的自主性、自私性等问题；例如网格节点都希望贡献较少的资源而尽可能多地使用其它节点的资源，或者贡献了资源而不保证资源的可靠性。因此需要引入网格信任理论，建立基于节点信任度的网格资源分配体系。那么将信任体系运用到网格定价机制中，保障资源分配公平，高效和安全可靠的进行是一个可行而且有必要的研究领域[22][23]。现阶段信任度在反应网格安全方面表现出了很好的特性，但是在反应服务质量方面存在诸多问题，很多学者引入了很多思想，其中比较突出的是多维度信任度模型的研究。多维度信任度的核心思想是:将服务质量用多个属性来表示，不同属性反应服务质量的不同方面，这样可以降低信任度的主观性，但是多维信任度的研究仍有很多问题，比如，怎样准确计算多维信任度的等价信任度，应该怎样选取哪些属性才能反应更真实的服务质量等等[27-32]。
1.3 本文的研究内容
本文的主要工作是对现有的组合双向拍卖机制进行改进，同时将信任机制引入到组合双向拍卖的网格资源调度机制中来，并对组合双向拍卖机制在机制策略上进行改进。具体的工作包括如下几个方面：
(1) 网格资源拍卖中，节点的单一角色问题使得资源不平衡的同时拍卖效率低、拍卖效用并非最优。本文将同一时刻所有节点或实体对资源的供需诉求全部进行拍卖，提出了混合组合双向拍卖机制，以求最大化拍卖效率和资源效用。
(2) 信任机制结合混合组合拍卖机制，提出基于信任与混合组合的双向拍卖的网格资源分配方法，结合了信任机制在安全性、服务质量等方面的特征，使得混合组合双向拍卖在最大化竞拍效率、保证资源合理分配合单位效用正向激励等具备很好的特性，该网格资源分配模型均优于已有方案。
(3) 针对基于信任与混合组合的双向拍卖的网格资源分配方案中竞胜标求解的NP难问题，提出了避开此环节而让所有的节点直接参与资源分配定价。另外，时间复杂度除了竞胜标求解导致外，还可能因为网格市场的资源类型过多导致。提出了针对资源类型拍卖的改进型方法。该方法在大规模数据环境、时间复杂度等方面有不错的优势。
1.4 论文结构
本文共包括五章，各部分的主要内容安排如下：
第1章：绪论
说明了信任机制与混合组合结合的网格资源调度研究的背景、意义以及国内外研究现状，并对本论文的主要研究工作和论文组织结构进行了说明。
第2章：相关研究综述
对现阶段信任机制研究、组合双向拍卖网格资源分配研究的研究进展进行了概述，主要包括：信任属性，网格定价机制，组合双向拍卖机制分析等。
第3章：基于混合组合双向拍卖模型研究
针对组合双向拍卖中网格节点或实体在单次拍卖中分别扮演资源提供者和资源需求者时所具有的不同特点，提出了混合组合双向拍卖模式，即在拍卖中节点本身不单是资源提供者同样也是资源需求者，这样一种模式使得节点或实体能将其对当前资源的需求或者供给诉求及时的到网格系统去参与资源调度分配。
第4章：基于信任与混合组合的双向拍卖网格资源分配研究
针对现有的组合双向拍卖模型的不足，提出混合组合模型的形式，并将信任机制引入到该模型中。信任度因子是通过价格调整函数来参与网格资源的分配，选取了幂指数是分母为奇数、分子为1的幂函数作为价格调整函数。在此基础上给出分配算法，从竞拍效率、交易效用和恶意节点鉴别等方面给做了详细的分析实验。
第5章：改进策略下的混合组合双向拍卖网格资源分配
该章节提出了完全区别于以往传统组合双向拍卖中网格市场只有单一拍卖师，该拍卖师负责网格市场所有的节点的资源分配与定价。同时传统拍卖机制中也存在求解竞胜标的NP难问题，这会导致很大的时间复杂度。改为采用多个拍卖代理机制，即资源拍卖代理。并就该方法在大规模数据、时间复杂度和拍卖效率等方面进行了仿真实验分析，获得了期望的实验结果。
总结与展望
总结了论文所完成的工作和研究工作中的不足。展望了未来组合双向拍卖、多维度信任机制的以及多维度信任机制在网格资源拍卖中的发展，并对下一步的研究工作提出了设想。
总结与展望
1 本文工作总结
本文旨在提出新的网格资源分配模型即混合组合双向拍卖，解决了以往文献中出现的诸多问题，将信任因子引入到网格资源分配的组合双向拍卖定价机制中，同时对该定价机制进行改进，是本文的核心工作，这样能够很好的弥补定价机制本身在安全性、服务质量等方面的不足，同时解决了上面提到的组合双向拍卖定价机制本身存在的诸多问题，另外，对于现阶段网格资源拍卖中机制的时间复杂度问题，提出了适应大规模网格数据量的改进策略的拍卖机制，并将这种机制结合了信任与混合组合双向的网格资源拍卖。
总结分析了现阶段拍卖机制运用于网格资源分配的各种模型，包括连续双向拍卖，组合双向拍卖，以及将两者结合起来的组合双向拍卖。在总结各模型的优劣性的同时重点对其表现出来的问题进行了认真的探讨，并且确定了组合双向拍卖在网格资源拍卖中独特的优越性以及面临的各种问题，为在下面章节中的研究工作展开了很好的铺垫，下文的工作正是针对此部分的问题进行一个个有针对性的解决，并作为三个章节来分开讨论研究。
提出了混合组合双向拍卖机制，针对在传统拍卖机制中节点扮演单一角色问题提出了混合组合双向拍卖机制，该机制提出在某一时刻，节点同时提出供给和需求诉求，即同时扮演买房和卖方、或者买方和卖方中的任意一方，这样买方节点的供给诉求和卖方节点的需求诉求都将在拍卖中得以实现，从而使得组合双向拍卖中的交易更加接近于最优交易，同时能够通过价格杠杆来调节竞争市场使得其保持良性循环。
提出了基于信任与混合组合双向拍卖的网格资源分配研究，将信任机制同混合组合双向拍卖结合到一起是本文的核心部分，信任机制的引进是通过信任度价格调整函数，该价格调整函数使得对于买家在信任阈值的左侧能够快速调低价格，在信任阈值的右侧能够快速调高价格；对于卖家在信任阈值的左侧能够快速调高价格，在信任阈值的右侧能够快速调低价格。信任机制在安全性、服务质量等方面的特征结合混合组合双向拍卖在最大化竞拍效率、保证资源合理分配合单位效用正向激励等优点，使得该网格资源分配模型均优于已有方案。
提出了一种改进策略下的组合双向拍卖网格资源分配方法，基于组合双向拍卖的网格资源分配一般分为两个步骤：竞胜标的选取确定和竞胜标的资源分配与定价。竞胜标的选取确定问题被证明是一个NP难的问题，现阶段很多文献对其进行了深入的分析研究，主要包括算法改进、优化以及机制的改良两大方面。本文将竞胜标的选取确定融合到竞胜标的资源分配与定价之中。并将对不同买卖方的代理转换成对不同资源的代理，在此基础上提出新的组合双向拍卖网格资源分配策略。
2 未来工作展望
网格资源分配的经济学模型在大量专家学者的努力下取得了非常不错的研究进展，并形成了一些理论体系，同时产出了一批发明、专利成果。但是同样还有一些值得去开拓的方面和领域，这些地方是现在网格资源分配的经济学模型的难点和瓶颈等。下一步研究工作将从以下几个方面寻找突破：
(1) 信任度机制的运用仅仅是针对信任度值的使用，没有具体到信任度的求解上，而现阶段的信任度求解趋于精细化的多维度计算。下一阶段可以尝试从基于偏好风险下求解信任度、以及信任度和其他属性之间的结合模型等。
(2) 本文的所有试验验证工作都是在Matlab的仿真平台上进行，下阶段可以尝试将本文研究的方案以及改进策略放到相对真实的网格仿真平台上，比如GridSim。
总之，网格资源的分配的发展同其他学科的发展一样不能只是在自己的领域闭门造车，应该多去研究、借鉴其他领域的相关知识，这样才能使得网格资源的分配的技术能够走得更加深远。