（计算机应用技术专业论文）网络资源交易与推荐模型研究.pdf

d i s s e r t a 6 0 ns u b m i t t e dt oz h e j i a n gu n i v e r s i 坶o f 1 、e c h n o l o g y f ；d rt h ed e g r e eo fm a s t e r r e s e a r c ho ng r i dr 电s o u r c et r a d i n g a n dl k c o m m e n d a 缸o nm o d e l c a n d i d a t e ：m e ix 往u e a d 订s o r ：p m f e s s o rh u a n gd e c a i c o u e g eo fc o m p u t e r s c i e n c ea n dr i e c h n o l o g y z h e j i a n gu n i v e r s i t yo f ，i e c h n o l o g y a p 瑚2 0 1 0 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究 工作所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其 他个人或集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其 它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡献的个人和 集体，均已在文中以明确方式标明。本人承担本声明的法律责任。 作者签名： 日期：洲。年s 月乃日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保拟 ( 请在以上相应方框内打“) 作者签名： 导师签名： 日期沙lo 年s 月) = ) 日 日期仉如年f 月7 了 渐江工业大学硕士学位论文 网格资源交易与推荐模型研究 摘要 网格是将地理上分布、异构的各种资源通过互联网连接并集成起来，形成一个对 用户相对透明的虚拟高性能计算环境，以实现资源的全面共享，巨大的应用前景使其 成为了近年来的研究热点。资源管理是网格系统的核心，对系统性能有着直接的影响。 随着经济学模型在网格资源管理领域的广泛应用，资源交易开始成为资源管理的新内 容。 本文针对现有资源交易模型在支付机制方面的不足，提出了一种新的通用资源交 易模型，并从减少响应时间、提高资源分配效率角度对模型进行了优化，主要工作包 括： 1 基于第三方支付的网格资源交易模型。模型中引入第三方对支付过程进行管 理与控制，达到安全交易的目的；同时，根据交易双方在交易过程中可能的恶意行为， 分析了模型中的危机处理机制，并给出引入危机处理机制下的支付流程。分析结果表 明该模型能有效处理交易双方的各种欺骗行为，避免支付过程的风险，确保交易双方 的经济利益。 2 基于最大9 距离子树的网格资源聚类。基于不同资源间的性能距离，将网格中 的所有资源进行聚类，得到性能各异的资源簇，使得资源发现机制在查找符合用户需 求的资源列表不再需要对网格的所有资源进行匹配。对资源进行聚类预处理可以将资 源匹配的范围从所有资源缩小到资源簇，从而大大减少资源匹配的耗时，提高资源分 配的效率。 3 基于聚类的网格资源推荐。针对由用户需求变化引起的网格系统负载不均问 题，提出一种资源推荐机制。充分利用较为空闲时段网格系统空余的计算能力，根据 用户历史交易记录评估特定资源与用户需求的相似度，为用户推荐相似度最大的 个资源，使得系统较忙时用户可以直接使用推荐的资源进行交易，无需等待系统的实 时分配。推荐机制实现了资源的提前分配，能有效缓解资源申请高峰时期系统的分配 浙江工业大学硕士学位论文 压力，减少用户等待时间。 关键词：交易模型，危机处理，资源聚类，相似度，资源推荐 浙江工业大学硕士学位论文 t h ei 乏e s e a r c ho ng i u di t e s o u c et r a d i n ga n d r e c o m m e n d a t l 0 nm o d e l a b s t r a c t g r i di sav i 删a 1 1 dl l i 曲一p e r f o 珊a n c ec o m p u t i n ge n v i r o m n e mw h i c hi sr e l a t i v e l y 舰l s p a r e m t 0u s e r s nc o i 】l l e c t sa n di n t e g ra ：c e sh u g e 姗o u n t so f g e o 野a p h i c a l l yd i s 仃i b u t e d a 1 1 dh e t e r o g e n e o u sr e s o u r c e st l l r o u g l li m e m e tw i t l lt l l e p u 印o s eo fa c h i e v i n gr e s o u r c e s h a r i n gg l o b a l l y o w i n gt 0i t s 擎e a ta p p l i c a t i o np r o s p e c t ，g r i dh a sb e c o m eah o t - s p o ti 1 1 r e c e n ty e a r s r - e s o u r c em a l l a g e m e n ti st h ek e m e lo fa 鲥ds y s t e ma 1 1 dh a sd i r e c ti m p a c to n s y s t e mp e r f o m a n c e w i t l lt 1 1 e 晰d e l yu s eo fe c o n o m i cm o d e l si nt 1 1 i sf i e l d ，r e s o u r c e 位l d i n gi st l 姗：1 i n gi m oan e wr e s e a r c hb i a n c ho fr e s o u r c em 柚a g e m e m a i m i n ga tm a b n gu pt 1 1 ed e f i c i e n c i e si nt h ea s p e c to fp a ) ，i n e n tm e c h a j l i s mo fe x i s t i n g r e s o u r c et r a d i n gm o d e l s ，an e wu 1 1 i v e r s a lr e s o u r c et r a d i n gm o d e lw a sp o 印o s e df o l l o w e d b yt 、v 0o p t i i n i z a t i o ns c h e m e s 1 ar e s o u r c et r a d i n gm o d e lb a s e do nt h i r d - p a r t y p a y m e n tm e c h a i l i s m b y i n 仃d d u c i n gam i r d p a 够t om a l l a g ea l l dc o m r o lt 1 1 ep a y m e mp r o c e s s ，t l l en e wm o d e lc 锄 i i l s u r es e c u r e 昀n a c t i o n s ac r i s i sm a n a g e m e n tm e c h a i l i s m 、a sa l s op r o v i d e di i lt l l em o d e l i n0 r d e rt oi d e n t i 匆t h ec h e a t i n ga c t i o n so f b o t l l 吐l e 仃a d i n gp a r t i e s a n a l y s i so ft l l em o d e l i n d i c a t e sm a tt l l en e wm o d e lc a l lh e l pt 0r e d u c et l l er i s kd u r i n gt 1 1 e 胁s a c t i o np r o c e s sa i l d m a x i m i z et 1 1 ee c o n o m i c sb e n e f i t so fb o t l lp r 0 v i d e r sa 1 1 dc o n s u m e r s 2 ar e s o u r c ec l u s t e rm e 也o db a s e do nm a x i m a l1 1 1 e t a - d i s t a n ts u b t r e e s t h em a i l l i d e ao fm i sp o i i l ti sc l u s t e 血gp r e p r o c e s s i i l gw i l i c hd e v i d e sa 1 1t 1 1 er e s o u r c e s 硫oc l u s t e r s 诵t t ld i 位r e n tp e d o m l a l l c eb a s e do nt l l ep e r f o r n l a l l c ed i s t a l l c eb e t w e e nv a r i o l l sr e s o u r c e s b yd o i n gt l l i s ，廿l e 鲥ds y s t e mo i l l yn e e dt 0s e a r c hi nt h ec l u s t e rt l l a tm o s tc l o s et 0t 1 1 e u s e r sd e m a l l di i l s t e a do fw h o l er e s o u i c ep o o lw h e ng e t c i l l gr e s o u r c el i s t sf o r 向r t b e r i 浙江工业大学硕士学位论文 r e s o u r c ea 1 1 0 c a t i o n c o n s e q u e n t l y ，c l u s t e rp r e p r o c e s s i n gc a i lg r e a t l yr e d u c e st l l et i m e c o n s 啪i n go fr e s o u r c em a t c h i n ga 1 1 di m p r o v et 1 1 ee m c i e n c yo fr e s o u r c ea l l o c a t i o n 3 ar e s o u r c er e c o m m e n d a t i o na 1 9 0 r i t h m t h ea 1 9 0 r i t h mw a sp r o p o s e di no r d e rt 0 b a l a i l c et l l es y s t e ml o a dc a u s e db yt l ：呛v a r i a t i o no fu s e rd e m a l l d s w i t l lt l l eh e l po f r e c o m m e n d a t i o na l g o r i t ，u s e r sa r ea l b et om 出汜仃a 1 1 a c t i o n s 谢t l lt l l er e s o u r c e s r e c o m m e n d e db yg r i ds y s t e md i r e c t l yw i m o u tm eo n - l i n ea l l o c a t i o no fg r i ds y s t e mw h e n t h es y s t e mi sb u s y b yi m p l e m e m i n gr e s o u r c ep r e a l l o c a t i o n ，r e c o m m e n d a t i o nm e c h a i l i s m c a ne 行i e c t i v e l yr e l i e f st l l es y s t e mp r e s s u r ed u r i n g 印p l yp ea ：ka n dr e d u c e su s e r s w a i t i n g t i m e k e yw 6 r d s ：觚1 s a c t i o nm o d e l ，c r i s i sm a i l a g e m e n t ，r e s o u r c ec l u s t e r i n g ，s i m i l 撕饥 r e s o u r c er e c o m m e n d a t i o n 浙江工业大学硕士学位论文 摘要 a b s t r a c t 第1 章绪论 目录 i i i i 1 1 研究背景l 1 1 1 网格l 1 1 2 网格资源管理一2 1 2 国内外研究现状3 1 2 1 基于经济机制的网格资源管理3 1 2 2 网格资源交易模型6 1 3 研究意义一7 1 4 研究内容8 1 5 论文组织结构9 1 6 本章小结l o 第2 章基于第三方支付的网格资源交易模型 l l 2 1 问题提出1 1 2 2 理论基础1 1 2 2 1 欺骗模型1 1 2 2 2 防欺骗算法1 2 2 3 基于第三方支付的资源交易模型1 3 2 4 模型中的安全机制分析1 4 2 。4 1 危机处理机制1 4 2 4 2 信誉机制1 7 2 5 模型优化18 2 5 1 资源聚类预处理18 2 5 2 基于聚类的资源推荐1 8 2 6 本章小结1 9 第3 章基于最大0 距离子树的网格资源聚类 3 1 问题提出。2 0 3 2 理论基础。2 0 v 浙江工业大学硕士学位论文 3 2 1 聚类算法概述2 0 3 2 2 基于最大0 距离子树的聚类算法2 l 3 3 网格资源与任务模型2 3 3 4 基于最大e 距离子树的网格资源聚类2 4 3 。4 1资源最小生成树构建2 4 3 4 2 资源簇生成2 6 3 4 3 基于聚类的资源分配2 7 3 5 仿真实验与分析2 8 3 5 1 实验环境设置2 8 3 5 2 实验结果与分析2 8 3 6 本章小结3 2 第4 章基于资源聚类的网格资源推荐 4 1 问题提出3 3 4 2 理论基础3 3 4 2 1 推荐技术概述3 3 4 2 2 基于项目的协同推荐3 4 4 3 用户需求量及资源状态预测3 5 4 4 基于资源聚类的资源推荐算法3 7 4 4 1问题描述3 7 4 4 2 资源簇确定3 8 4 4 3t o p n 资源确定一3 9 4 4 4 算法描述4 0 4 5 仿真实验与分析4 2 4 5 1 实验环境设置。4 2 4 5 2 实验结果与分析4 2 4 6 本章小结4 5 第5 章总结和展望。4 6 5 1 本文主要成果4 6 5 2 存在的问题4 7 5 3 展望4 8 参考文献4 9 致谢。! ；! ； 攻读学位期间参加的科研项目与发表的论文5 6 v i 浙江工业大学硕士学位论文 第l 章绪论 1 1 研究背景 1 1 1 网格 过去，造价高昂的超级计算机往往被用来解决一些计算密集型问题，但随着 信息技术的迅猛发展，各个领域的计算需求不断增大，对于一些规模庞大、计算 复杂、需要用到多种异构资源的计算问题，单一的超级计算机已经不再具备解决 能力，我们迫切需要一种设施，来满足当今社会不断膨胀的计算需求。2 0 世纪9 0 年代中期，受电力网的广泛渗透性、易用性以及可靠性的启发，科学家们提出建 立一种类似于电力网的基础设施，用于广域网的并行与分布式计算【1 1 。用户可以 随意从中获取需要的服务，而不必关心其内部的管理与运作，就像使用电力一样 方便快捷。这个基础设施即称为网格( g m ) ，网格的提出迅速掀起了新一代互 联网技术的研究浪潮，得到了广泛的关注。 传统的万维网实现的是信息的交互，而网格关注的是资源的全面共享，它通 过互联网将地理上分布、异构的各种资源，如超级计算机、存储资源、数据资源、 专用设备等等组织起来，形成一个用户相对透明的虚拟的高性能计算环境【l 】。从 本质上讲，网格就是构建于广域网上的分布式计算系统，广域性、异构性、动态 性是它区别于传统的分布式系统的主要特点【2 1 。由于网格巨大的发展前景，欧美 一些发达国家以及h p 、i b m 等著名的公司都在网格基础设施的构建与网格系统 的开发上投入了大量的人力、物力与财力，其中著名的网格项目如美国的g 1 0 b u s ； 我国的网格研究也在如火如荼地进行，已经完成的项目如清华大学的a c i 系统与 中科院的国家高性能计算环境m p c e 【3 1 。近年来，网格主要应用于解决科学、工 程以及商业领域中的一些复杂的资源密集型问题，如卫星数据分析、电影特效渲 染、疾病研究等。随着网格的应用逐步走向商业化，其成为一种全球性的服务提 供机制指日可待。 浙江工业大学硕士学位论文 1 1 2 网格资源管理 要构建一个网格系统，需要研究实现一系列的服务，如安全、资源目录、工 具与应用、资源管理等，而资源管理是其中最主要也是最富挑战性的方面【4 】【5 1 。 资源管理的基本功能是接收网格用户的资源需求，并分配合适的资源为其服务， 它包含了资源发现，资源分配以及任务的执行这样一个过程。资源发现就是根据 用户对资源的需求描述，在众多异构、动态的资源中进行匹配，最后返回符合用 户需求的一组资源。资源分配则是在资源发现返回的资源列表基础上，以某种目 标确定最终执行任务的某个资源。可以说，资源发现是资源分配的基础，资源分 配是资源管理的核心，资源分配效率的高低对网格系统的效用有重要的影响【6 】。 网格资源分布各地，分属于不同的组织机构，具有动态性、自治性等特点， 而且资源消费者往往拥有不同的喜好，这些使得网格资源的管理变得尤为复杂。 根据资源分配遵循的分配目标不同，可以将常用的资源管理策略分为以系统为中 心与以用户为中心两类【7 】。以系统为中心的资源管理是一种比较传统的策略，它 从全局的角度考虑问题，试图最优化整个系统的性能，往往用于管理单一管理域 的资源。基于这种管理策略的网格资源管理系统【8 】【9 】在进行资源分配时一般以系 统性能参数驱动的代价函数为依据，旨在提高系统的吞吐率、利用率并且使得任 务总体完成的时间最短，而忽略了单个任务的执行情况。同时，它不考虑资源的 价格，也就是说任务在任意时刻访问不同资源的代价都是一样的，这种假定不符 合实际情况，比如性能较高的资源应该比性能相对较低的资源具有更高的访问价 格。以用户为中心的资源管理则刚好相反，它关注的是网格用户的q o s 需求，旨 在向用户交付高质量的服务。要保证网格资源的服务质量，就要求系统能根据资 源提供的服务情况给予相应的奖励或惩罚，因此，以用户为中心的管理策略大多 引入经济学理论对资源进行管理【l o 】。这种管理策略下，资源具有访问价格，系 统基于各种经济学模型为用户实施资源分配，用户必须为其使用的资源付费，而 资源提供者只有按照用户的q o s 需求提交服务才能获得相应的报酬。 随着网格技术的不断推广，网格资源的服务质量受到了越来越多的关注，成 为了网格系统中的一个关键因素【1 1 】，因此以用户为中心的资源管理将是网格资 源管理的主要方向。研究社会资源配置的经济学理论为管理分布、异构的网格资 源提供了一个公平公正的基础，有利于保证网格系统的稳定性和有效性，这些优 2 浙江工业大学硕士学位论文 势使得基于经济机制的资源管理成为了近年来的研究热点【1 2 】【1 3 】。 1 2 国内外研究现状 1 2 1基于经济机制的网格资源管理 迄今为止，已有多种经济学模型被应用于网格资源管理领域，包括：商品市 场模型、标价模型、投标网模型、拍卖模型以及议价模型【1 4 】。 商品市场模型中，资源提供者指定自身服务的价格，并根据消费者使用的服 务量收取费用。服务的价格通常由多个参数共同决定，比如网格平台的费用、用 户使用的时长( 即任务执行的时间) 、资源的供需情况。价格可以是固定的或者 根据供需变化上下浮动，当用户需求增加或者市场供应减少时，价格会上调直至 恢复供需平衡。消费者根据服务的价格访问各种资源，在向系统提交任务时，消 费者可以设定任务的需求，比如任务完成的截止期限与预算，管理者在进行资源 分配时首先确定满足用户需求的资源，并向资源的提供者获取其服务价格，再为 用户分配其中费用较低的资源。基于该模型的资源管理系统如e n h a i l c e d m o s i x 【1 5 】、n i l l l r o d g 【1 6 1 、g c o m m e r c e f l 7 1 ，其中e 1 1 l a i l c e dm o s i x 在任务执行过 程中还支持任务的迁移，以保持任务执行的总代价处于较低的水平。 标价模型与商品市场模型类似，区别在于某些资源提供者会通过一些优惠方 式来吸引用户，比如某时段提供5 的折扣或5 m b 以内的存储空间免费使用等。 这种模型下，管理者不需要通过与资源提供者的交涉来获取服务的价格，只需要 根据资源提供者标定的价格实施分配，而且这个价格通常要低于常规价格。尽管 标价的资源有一定的使用限制，但低廉的价格对某些用户来说具备一定的吸引 力。比如，节假日期间资源的需求量一般要少于工作日，此时资源提供者就可以 通过临时的优惠价格来吸引用户，以提高资源的利用率。支持该经济模型的资源 管理系统如n i m r o 彤g 【1 6 】。 投标网模型也称合同网模型，是分布式计算环境中服务协商最常用的模型之 一，它仿照商业中用于管理商品与服务交换的合同机制构建，有助于为给定的任 务找到合适的服务提供商。这种模型下，资源消费者( 招标人) 以招标文件的形 式在网格市场中发布需求，招标文件包含招标要求( 如投标人需具备l i l l u ) 【系统， 浙江工业大学硕士学位论文 1 2 8 m b 内存) 、任务简介、预算金额、投标说明( 投标书应包含的内容) 以及截 止期限( 接收投标书的最晚时间) 等。资源提供者( 投标人) 从网格市场获取招 标文件，分析判断自身的服务能力是否符合招标要求，若满足要求则在截止期限 前向管理者提交投标书。管理者评估多份投标书，确定最后的中标者。某些情况 下，管理者可能收不到某份招标文件的投标书，比如：( a ) 所有符合要求的资源 提供者正忙；( b ) 资源提供者空闲但是对其他的招标文件更感兴趣；( c ) 没有符 合招标要求的资源提供者。为避免这种情况，管理者可以要求投标人在回复正式 投标书之前先向管理者作一个快速响应，告知管理者自身的状态：符合招标要求、 正忙、不符合招标要求或不感兴趣。招标人可以根据各投标人的响应信息修改自 身的工作计划，如推迟截止期限或增加预算，以吸引更多的投标者。基于该经济 模型的资源管理系统如：m a r i p o s a 【1 8 】、j a w s 【1 9 1 。 拍卖模型在现实生活中的应用非常广泛，尤其是在收藏品行业，它通过多个 买方之间的竞价交易实现商品的最大价值。拍卖的方式有单向与双向之分，单向 拍卖中主要的拍卖方式包括英式、荷兰式、最高叫价密封拍卖、c h e y 拍卖( 次 高叫价密封拍卖) 以及组合拍卖f 2 们，不同拍卖方式下的拍卖规则各不相同。单 向拍卖支持一对多的协商，基于单向拍卖的资源管理中，资源提供者为委托人， 资源消费者为竞买人，管理者则充当拍卖商的角色。管理者制定资源提供者与消 费者均可接受的拍卖规则，资源提供者发布服务并接受资源消费者的出价，管理 者控制整个竞拍的过程，出价最高者获得服务的使用权。s p a v m 【2 1j 采用了c k r e y 拍卖方式来管理异构工作站网络中的资源，p o p c o m 【2 2 】贝0 采用英式拍卖实现基于 w r e b 的在线资源分配。与单向拍卖不同，双向拍卖支持多对多的协商，即同一种 商品存在多个卖方，多个买方与卖方可以同时对某一商品以暗标( 其他人无法获 知本方的出价) 的形式出价，由拍卖商对双方的出价进行匹配，出价一致的一对 买方与卖方即达成交易。网格市场就符合多对多的特征，因此近年来双向拍卖模 型在网格资源管理中的应用备受关注【2 3 之5 1 。文献 2 6 2 8 则结合了双向拍卖与单向 拍卖中的组合拍卖，使得资源消费者可以对不同种类与数量的资源组合进行双向 投标，大大降低了交易成本，提高了资源分配的效率。 议价模型与前面提到的经济模型存在本质的差别。这些经济模型中，资源提 供者对服务价格的制定具有主导权，而且管理者会对整个资源分配过程进行协调 4 浙江工业大学硕士学位论文 管理；但议价模型中资源的价格由资源提供者与资源消费者协商确定，且管理者 仅仅提供一个供资源提供者发布资源信息的平台，并不实质性参与资源分配过程 【2 9 1 。在议价过程的开始，资源消费者对其感兴趣的资源给出一个较低的价格， 而该资源的提供者对其定价可能很高。随后，双方以特定的松弛策略逐步降低各 自的要求，直到双方达成一致或者其中一方中止协商，整个协商过程由交易双方 独立进行，不需要管理者的干预。一个资源消费者可以同时与多个资源提供者进 行协商，以便从中选择费用最低的资源，报价较高的资源提供者为了赢得订单不 得不降低售价；另一方面，一个资源提供者同样有多个资源消费者参与竞争，报 价过低的资源消费者为了完成任务必须提高自己的报价。因此，议价模型能够帮 助交易双方实现利益最大化，而且高度自治的协商过程避免了管理者对交易对象 的统一控制，能有效解决不同的交易对象在交易目标、访问策略及供需模型等方 面存在的差异，是一种有效的网格资源管理方法【3 0 。3 2 1 。 此外，其他经济学模型如基于投标的资源共享模型【3 3 】及宏观经济学模型【3 4 】 也曾被应用到资源管理领域。这些经济学模型中，拍卖模型与议价模型是近年来 研究较多的，基于这两种模型的资源交易过程分别如图1 1 与图1 2 所示。 ui 篁氏 ( 1 m 地g o c i a l 聪f o r t i 地 b l p 妇) g d m a r k e t e r e c t o r y ( g m d ) 熙 塌 回器ll 固l 黑劣 图1 1基于议价的资源交易模型 浙江工业大学硕士学位论文 图1 2 基于单向拍卖的资源交易模型 1 2 2网格资源交易模型 对基于经济机制的网格资源管理的一系列研究证实了经济学模型在管理网 格资源中的有效性，同时也给传统的资源管理引入了新的研究内容：资源交易与 基于q o s 的任务调度【l 引。要解决这些新问题，一个基于经济学的网格系统必须 提供以下服务：用于发布网格资源信息的市场目录；资源定价与发布机制； 经济学模型与协商协议：市场监管员，负责交易标准的制定以及交易过程中 的危机处理；交易账户设置、账单服务及支付机制；用户q o s 需求驱动的 调度系统。本文主要研究资源交易相关的一些内容，暂不考虑任务的调度。 资源交易包含了从任务的提交、资源的分配、任务执行到费用的支付这一整 个过程，它涵盖了比传统资源管理更加广泛的内容。上一节介绍了现有的一些基 于经济机制的资源管理模型，这些研究引入经济学模型作为资源分配过程中的资 源定价与协商协议，以此来保障交易双方的经济利益。它们的研究重心都是如何 利用经济学模型实现有效的资源分配，而缺乏对交易模型中支付机制的研究。文 献【3 5 j 提出了一种通用的网格资源交易模型，并对整个交易过程进行了详细地阐 述。该模型下的支付方式是由资源消费者在收到资源提供者返回的计算结果后， 将费用划入对方在网格银行中的账户。这就要求资源消费者是诚信的，他们能够 按照资源提供者的服务情况支付费用，但这往往是不现实的，在利益的驱使下， 6 零零零零 一。删一 一。：詈 浙江工业大学硕士学位论文 不光是资源消费者，交易双方均有可能存在恶意行为。一些学者【3 阳提出使用信 誉度来表示交易双方的可靠性，在资源交易过程中优先选择信誉度较高的交易对 象。这种方式确实能提高网格市场的成功交易率，但是信誉度高的交易对象未必 不会在本次交易中实施欺骗，因此仍然不能确保支付过程的安全可靠。文献眇】 提出了一种基于赔偿的资源交易模型，引入了第三方对支付过程进行管理与控 制，但文章的主旨是通过资源提供者承诺的赔偿金额来识别资源提供者的可靠 性，并未对第三方如何保证支付安全作具体说明。因此，资源交易模型中有效的 支付机制仍是当前研究相对欠缺的方面。 1 3 研究意义 网格是新一代的互联网技术，是当今社会飞速发展下的产物，其巨大的应用 前景使得众多国家与企业纷纷设立自己的网格项目。随着网格的应用走向商业 化，其将成为一种全球性的服务提供机制。资源管理是网格系统的核心技术，其 主要包含了资源发现与资源分配，资源发现是资源分配的基础，资源分配效率的 高低直接影响了网格系统的性能。鉴于社会资源配置与网格资源分配的相似性， 越来越多的学者将研究社会资源配置的经济学模型应用到网格资源管理领域，并 取得了一定的成果。网格的商业化导向决定了基于经济机制的资源管理将成为网 格系统不可或缺的部分，而经济化的资源管理也使得传统的资源管理模型开始向 资源交易模型转化，资源交易成为了资源管理的新内容。一个好的资源交易模型 应能在实现有效资源分配的同时保障交易过程的安全可靠，以保障交易双方的经 济利益，从而提高用户对网格系统的忠诚度，吸引更多的用户积极参与到网格系 统的应用，实现网格技术的快速推广。现有的对网格资源交易模型的研究虽然取 得了一定的进展，但对于一些关键问题仍然没有好的解决办法，本文对交易模型 的研究正是基于这些缺陷与不足开展的。文中对存在的问题进行了详细描述，同 时给出了相应的解决方案并通过仿真实验验证了方案的有效性，所得出的实验结 果与分析以及引入的其他领域的一些关键技术，都可以作为后续研究及系统实现 的理论基础与参考依据，具有十分重要的意义。 7 浙江工业大学硕士学位论文 1 4 研究内容 本文旨在改进现有资源交易模型在支付机制方面的不足，提出一种新的资源 交易模型，增加对支付过程的管理与控制，提高交易过程的可靠性；同时，为了 提高资源分配的效率，减少资源分配的响应时间，从两个方面对交易模型进行了 优化。本文的研究内容主要包括以下几点： 1 、基于第三方支付的网格资源交易模型 基于经济机制的资源管理赋予了网格资源一个新的属性价格，资源提供 者有偿提供空闲的资源，资源消费者为使用的资源支付相应的费用，如何安全可 靠地实现付费的过程便是支付机制要解决的主要问题。由于网格资源的交易双方 都是虚拟的节点，双方对相互的信用状况没有直接的了解，资源提供者为了确保 任务执行后能得到预期的回报，要求资源消费者先向其支付费用；而资源消费者 为了防止资源提供者在收到付款后不提供约定的服务，则要求在服务完毕后再支 付费用，这显然构成了一种矛盾。因此，本文提出一种新的资源交易模型，引入 具有公信力的第三方来对支付过程进行管理，资源消费者先将费用支付给第三 方，由第三方在任务执行完毕后根据任务完成情况将费用支付给资源提供者或退 还给资源消费者，避免了支付过程的风险。 2 、基于最大e 距离子树的网格资源聚类 资源发现是资源分配的基础，它负责在众多网格资源中查找出符合用户需求 的资源列表。网格的主旨是实现资源的共享，它囊括了各种异构的资源，数量众 多且性能各异，对如此庞大的资源群进行匹配往往要耗费大量的时间，使得资源 发现成为了限制资源分配效率的一大因素。因此，本文考虑对所有在网格中注册 的资源作一个聚类预处理，以资源间的性能距离作为衡量指标对资源进行聚类， 得到性能各异的资源簇，使得簇内资源的性能相似，而簇间资源的性能差异较大。 资源发现在进行资源查找时首先确定与用户需求最接近的资源簇，再对簇内的资 源进行进一步匹配。由于单个资源簇内的资源数量要远远小于整个网格系统的资 源数量，这一举措能大大提高资源发现的效率。 3 、基于资源聚类的网格资源推荐 同现实市场一样，网格市场中也存在着用户需求的变化。当用户需求较小， 远远低于网格系统的负载能力时，用户往往能在很短的时间内得到响应；相反， 8 浙江工业大学硕士学位论文 当到达资源申请高峰时，用户的响应时间会大大增加，从而降低了用户的满意度 以及资源的利用率。一方是空闲时期系统多余计算能力的浪费，一方是高峰时期 系统的超负荷工作，能否在空闲时期提前为将要到来的高峰期作好资源分配，缓 解高峰期系统的分配压力，是本文研究的另一个重点内容。本文尝试将电子商务 中常用的推荐技术进行拓展，引入到资源分配领域，通过用户的历史交易记录推 测用户对特定资源的喜好程度，为用户推荐其可能感兴趣的资源，使得部分用户 在高峰期可以直接使用推荐的资源进行交易，而不必等待系统的实时分配，达到 平衡系统负载的目的。 1 5 论文组织结构 论文的组织结构安排如下： 第一章首先简单介绍了网格相关的一些背景知识，如网格的概念、特点及 网格资源管理的涵义；然后对基于经济机制的网格资源管理模型与资源交易模型 的国内外研究现状作了详细说明；最后给出本文的研究意义、研究内容及论文的 组织结构。 第二章介绍了本文提出的基于第三方支付的网格资源交易模型，并详细阐 述了基于该模型的资源交易过程；同时，针对资源提供者与消费者可能的恶意行 为，给出了本模型的危机处理机制，确保交易过程的安全可靠；最后，从减少资 源分配响应时间、提高分配效率角度提出了模型的两种优化方案。 第三章主要介绍模型的优化方案资源聚类的相关内容。首先，在概述 现有的资源聚类算法基础了简单介绍了基于最大0 距离子树聚类算法的基本步 骤；随后从资源性能距离的计算、资源最小生成树构建以及资源簇的生成等方面 详细阐述了基于最大e 距离子树的网格资源聚类的实现，并描述了在聚类基础上 实施资源分配的基本步骤；最后对资源聚类及基于聚类的资源分配进行了仿真实 验。 第四章主要介绍模型另一个优化方案资源推荐。首先，对电子商务领 域中的推荐技术尤其是基于项目的协同推荐方法作了简单介绍；然后借鉴基于项 目的卸- 推荐算法的基本思想，提出了基于聚类的网格资源推荐算法，逐步介 9 浙江工业大学硕士学位论文 绍了算法的基本步骤并给出算法的伪代码，同时对算法的计算复杂度进行分析； 最后是仿真实验及结果分析。 第五章论文的总结，详细阐述了论文的主要贡献及研究中存在的一些不足， 并展望了网格资源交易模型研究的下一步工作。 1 6 本章小结 本章首先介绍了网格与网格资源管理相关的一些背景知识，使得读者能对网 格系统、资源管理在网格系统中的核心地位及其发展趋势有个大致的了解；接着 详细阐述了基于经济机制资源管理与资源交易模型的国内外研究现状，并指出了 现有研究存在的缺陷与不足，为本文的研究内容的提出奠定基础；随后针对存在 的问题引出本文的研究意义及研究内容；最后对论文的组织结构作了简单介绍， 使得读者能更全面地把握全文的主要内容。 l o 浙江工业大学硕士学位论文 第2 章基于第三方支付的网格资源交易模型 2 1 问题提出 在基于经济机制的网格资源管理中，各种资源具有相应的“价格 。但资源 交易双方，即资源提供者与消费者都是虚拟的结点，双方对相互的信用情况没有 直接的了解。若选择先付款，则资源消费者选择资源并付费后，任务可能得不到 预期的执行，相反，若采取后付款的策略，则资源提供者必须承担执行任务后得 不到预期回报的风险。根据第一章的描述，现有的大部分资源交易模型的研究重 点是如何利用一些经济模型实现有效的资源分配，使得交易双方的经济利益最大 化，而往往忽略了对交易模型中支付机制的研究。文献【3 5 】提出一种通用的资源 交易模型，并详细阐述了包括支付方式在内的整个交易过程，但没有考虑资源消 费者的可靠性。其他一些研究【3 6 3 8 1 提出使用信誉度来表示交易双方的可靠性，以 减少交易风险，这种方式虽然提高了网格市场的成功交易率，但信誉度只能作为 一种参考而不能作为一种保障，信誉度高的交易对象未必不会在本次交易中实施 欺骗，因此仍然不能确保支付过程的安全可靠。 为解决网格资源交易过程中的这种不安全性，本章提出一种基于第三方支付 的网格资源交易模型，引入第三方对交易过程进行管理与控制，在保障交易安全 的同时，结合信誉度模型，对交易双方进行评价，来提高网格市场的成功交易率。 2 2 理论基础 2 2 1欺骗模型 对于域d = 缸1 ，砣而) ，假设网格资源提供者的计算任务是计算映射 少= 厂( x ) ，x d ，资源提供者可能为了很多目的去欺骗，文献【4 0 】将欺骗归为下列 两大类： 半诚实欺骗模型：在这种模型中，资源提供者通过降低计算量来实施欺骗， 浙江工业大学硕士学位论文 即他所计算的域是x d ，而d cd ，对于其余的x ( d d ) ，则用厂( x ) 来代 替。与函数厂相比，函数厂往往能节约计算时间。例如，厂可能仅仅是个猜测 值。这种欺骗方式能帮助资源提供者在相同的时间里完成更多的计算任务，并以 此获取更多的利润。 完全欺骗模型：在这种模型中，资源提供者的欺骗方式则比较随意。例如， 一个恶意的资源提供者可能按照资源消费者的要求对所有的x d 进行了计算， 但是他故意将错误的计算结果返回给消费者，以此来干扰消费者。 2 2 2 防欺骗算法 防欺骗算法顾名思义是指用来检测资源提供方欺骗行为的方法，一些典型的 防欺骗算法如简单样本方案、鼬n g e r s 方案【4 l 】、基于承诺的样本检验方案【4 0 】【4 2 1 等。 简单样本方案的基本原理是对计算结果进行二次验证。管理者从域d 中随 机抽取少量的样本，重新计算这些样本对应的厂值，并与资源提供者提供的结果 进行比较，若两者不一致，就可以认为资源提供者存在欺骗行