（计算机应用技术专业论文）基于vague集的网格资源发现模型.pdf

浙江工业大学硕士学位论文 基于v a g u e 集的网格资源发现模型 摘要 资源发现是网格技术的一个非常重要的方面，资源发现就是找到与预想的资 源描述相匹配的资源。网格资源的发现方式必须能够适应具有大规模、异构性、 分布性、动态性、开放性等特点的网格环境。如何将资源有效地组织起来，并高 效地发现和定位资源已经成为一个非常重要的问题。 当前对网格资源匹配的研究主要集中于精确匹配，而在模糊匹配方面做的 研究较少。在p 2 p ( p e e r - t o p e e r ) 的环境下，大部分参与者都是自私的，他们不会 主动地贡献自己的资源。此外，有些参与者可能会擅自夸大自己提供资源的能力 来获取更多的利益。针对当前网格资源发现存在的这些问题，本文建立了一种能 支持基于v a g u e 集的模糊匹配机制的p 2 p 网格资源发现模型。本文主要在以下几 个方面做了一些贡献： 一、由于结构化p 2 p 模型只支持精确匹配查询，而且它们都不支持直接的关 键词搜索，因此本文在非结构化p 2 p 模型g n u t e l l a 基础上进行改进，得到能够支持 基于v a g u e 集的模糊匹配机制的m s r 三层资源发现模型，该模型的资源发现性能 l ：l g n u t e l l a 模型有大幅度提升。 二、本文把v a g u e 集理论应用到资源的描述和匹配过程中。v a g u e 集能够很 好地表达资源请求者所需资源的模糊信息。当用户请求的资源与资源节点提供的 资源进行匹配时，通过计算两者之间的相似度来判定它们是否匹配。这种匹配方 法，可以根据用户的需求和满意度，设置不同相似度阈值，从而提高了资源发现 的灵活度。 三、现有的激励机制主要通过整数值来描述本地信任值等模糊的衡量指标， 难免会导致描述的失真。由于v a g u e 集能够很好地描述和处理模糊信息，因此本 文用v a g u e 集表示的信任度来描述资源节点的可信程度，通过基于v a g u e 集的激励 机制和惩罚机制动态更新资源节点的信任度，减少恶意节点对资源发现过程造成 浙江工业大学硕士学位论文 的危害，鼓励优质的资源节点加入网格当中。 最后，本文还结合激励机制和惩罚机制对基于v a g u e 集的资源匹配算法做进 一步地改进。仿真实验表明引入激励机制和惩罚机制后，模型的资源发现性能得 到明显提高。 关键词：资源发现，v a g u e 集，p 2 p ，匹配，相似度 浙江工业大学硕士学位论文 g r i dr e s o u r c ed i s c o v e r ym o d e l b a s e do nv a g u es e t a b s t r a c t r e s o u r c ed i s c o v e r yi sa ni m p o r t a n ta s p e c to fg r i d r e s o u r c ed i s c o v e r yi st of i n d t h er e s o u r c em a t c h i n gt h ee x p e c t e dr e s o u r c e h o wt oo r g a n i z et h er e s o u r c ee f f e c t i v e l y , t h e nf i n da n dl o c a t et h er e s o u r c ee f f i c i e n t l yh a sb e c o m ea v e r yi m p o r t a n tp r o b l e m c u r r e n t l y , t h er e s e a r c h e sa b o u tm a t c h i n go f 面dr e s o u r c ef o c u so ne x a c t m a t c h i n g ，b u td oal i t t l ew o r ka b o u t 呦m a t c h i n g i nt h ep 2 p ( p e e r - t o p e e r ) s u r r o u n d i n g ，m o s to ft h ep a r t i c i p a n t sa r ea l ls e l f i s h , s ot h e yw o n to f f e rt h e i rr e s o u r c e f o r w a r d l y w h a t sm o r e ，s o m ep a r t i c i p a n t sw i l le x a g g e r a t et h e i ra b i l i t yi no r d e rt og e t m o r eb e n e f i t t h i sp a p e re s t a b l i s h e sap 2 pg r i dr e s o u r c ed i s c o v e r ym o d e lw h i c hc a n s u p p o r tf u z z ym a t c h i n gm e c h a n i s mb a s e do nv a g u es e ti no r d e rt os o l v et h ep r o b l e m s e x i s t i n gi n t h e c u r r e n tg r i dr e s o u r c e d i s c o v e r y t h e r e s e a r c hh a sd o n es o m e c o n t r i b u t i o na sf o l l o w s ： f i r s t l y , b e c a u s es t r u c t u r e dp 2 pr e s o u r c ed i s c o v e r ym o d e l so n l ys u p p o r te x a c t m a t c h i n ga n dd o n t s u p p o r ts e a r c h i n gb yk e y w o r d ，t h i sp a p e ri m p r o v e st h e u n s t r u c t u r e dp 2 pr e s o u r c ed i s c o v e r ym o d e lg n u t e l l aa n dg e t sam s rt h r e el a y e r r e s o u r c ed i s c o v e r ym o d e l ，w h i c hc a ns u p p o r tf u z z ym a t c h i n gm e c h a n i s mb a s e do n v a g u es e t a n dt h em o d e lh a sb e t t e re f f i c i e n c yo fr e s o u r c ed i s c o v e r yt h a ng n u t e l l a s e c o n d l y , t h i sp a p e ra p p l i e sv a g u es e tt h e o r yi n t ot h ed e s c r i p t i o no fr e s o u r c ea n d t h ep r o c e s so fm a t c h i n g v a g u es e tc a ne x p r e s st h ef u z z yi n f o r m a t i o no ft h er e s o u r c e r e q u i r e db y t i g e r se f f e c t i v e l y t h r o u g hc o m p u t i n gt h es i m i l a r i t yb e t w e e nt h er e s o u r c e r e q u i r e db yu s e r sa n dt h er e s o u r c eo f f e r e db yr e s o u r c en o d e ，w ec a l lg e tw h e t h e rt h e y m a t c h t h i sm e t h o dc a l lb es e td i f f e r e n t s i m i l a r i t yv a l u ea c c o r d i n gt ou s e r s r e q u i r e m e n ta n ds a t i s f a c t i o nt oi n c r e a s et h ec o n v e n i e n c eo fr e s o u r c ed i s c o v e r y i i i 浙江工业大学硕士学位论文 t h i r d l y , c u r r e n ti n c e n t i v em e c h a n i s m sm o s td e p i c tt h ef u z z yi n d e xs u c ha sl o c a l c r e d i tw i t hi n t e g e r ，w h i c hc a n ta v o i dd i s t o r t i o no ft h ed e p i c t i o n b e c a u s ev a g u es e t c o a ld e p i c ta n dp r o c e s sf u z z yi n f o r m a t i o nv e r yw e l l ，t h i sp a p e ru s e sc r e d i tt h a ti s r e p r e s e n t e db yv a g u es e tt od e p i c tt h er e s o u r c en o d e s c r e d i b i l i t y , a n di n t r o d u c e s c o r r e s p o n d i n gi n c e n t i v em e c h a n i s ma n dp e n a l t ym e c h a n i s mt ou p d a t et h ec r e d i to f r e s o u r c en o d e si no r d e rt od e c r e a s et h ev i c i o u sn o d e s h a r mt or e s o u r c ed i s c o v e r ya n d e n c o u r a g em o r eg o o dr e s o u r c en o d e st oj o i ni nt h eg d d f i n a l l y ，t h i sp a p e ri m p r o v e st h er e s o u r c em a t c h i n ga l g o r i t h mw h i c hi sb a s e do n v a g u es e t w i t hi n c e n t i v em e c h a n i s ma n dp e n a l t ym e c h a n i s m s i m u l a t i o nt e s t d e m o n s t r a t e st h a tt h ei n t r o d u c t i o no fi n c e n t i v em e c h a n i s ma n dp e n a l t ym e c h a n i s m i n c r e a s e st h em o d e l sc a p a b i l i t yo fd i s c o v e f i n gr e s o u r c eo b v i o u s l y k e yw o r d s ：r e s o u r c ed i s c o v e r y , v a g u es e t ，p 2 p , m a t c h i n g ，s i m i l a r i t y 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研 究工作所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包 含其他个人或集体已经发表或撰写过的研究成果，也不含为获得浙江工业大 学或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡献 的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律责任。 作者签名：羽1 芳纪日期：沙务7 z 月zz 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权浙江工业大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本 学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密阢 ( 请在以上相应方框内打“”) 作者签名：羽、靓 刷谧轹坼_ 日期：沙。7 年肛月易z 日 日期：沙。7 年，2 月参l 日 浙江工业大学硕士学位论文 1 1 研究背景 第1 章绪论 随着网络技术的高速发展，应用需求的日益增长，网格( g a d ) 技术应运而生。 它代表了继i n t e m e t 技术和w e b 技术之后的第三次互联网技术浪潮，引起了政府、 学术界和工业界的高度重视。 关于网格的定义有很多，其中网格技术的权威i a nf o s t e r 提出网格必须同时 满足三个条件【l 】：在非集中控制的环境中协同使用资源；使用标准的、开放的和 通用的协议与接口；提供非平凡的服务。可以说网格就是一个集成的计算与资源 环境，网格技术是对网络增加了许多新的协议和服务的下一代i n t e m e t 技术 2 1 。 作为互联网技术发展的一个方面，网格是广域的、大规模的分布式环境，它 具有如下特点：( 1 ) 网格资源地理分布极广，资源之间、资源和使用者之间往往 通过广域网连接。( 2 ) 资源以及网格的状态是动态变化的。( 3 ) 作为一种公共基 础设施，网格资源的数量巨大。( 4 ) 网格用户数量巨大。由于网格是分布在广域 网上的，受网络带宽、网络延迟和网络不可靠性的影响，网格资源的定位将很大 程度上影响网格计算的性能。网格是一个动态的环境，它利用遍布全球的闲置资 源，网格资源可以随时加入或退出网格系统，同时，受本地作业的影响，网格资 源的可用度也是不断变化的，所以需要种有效的资源发现机制来及时发现网格 系统中满足作业要求的可用网格资源【3 1 3 。所谓的资源发现就是资源请求者给定一 个预想的资源描述，一个资源发现机制将返回一组与描述相匹配的资源。而资源 发现机制就是在对多样的、异构的、动态的资源合理组织的基础上，为用户查找 和访问所需资源提供有效的资源发现服务，最终根据用户的资源发现请求返回一 系列符合需求的资源描述信息的信息服务机制。 随着网格规模越来越大，网格资源的种类越来越多，网络结构也越来越复杂， 使得网格资源查找变得异常复杂，很难准确快速地找到符合用户需求的资源。网 浙江工业大学硕士学位论文 格资源发现作为网格系统中一项非常关键的技术，对网格系统的资源共享起到至 关重要的作用，因而资源发现技术面临着越来越大的研究挑战。网格资源发现研 究的意义 4 1 主要体现在： l 、资源发现是资源共享的基础，对后续使用共享资源以及整个系统性能有 重大的影响。 随着网络规模的扩大，应用的增多，资源种类和数量的急剧增长，网络上资 源的状态也在不断变化，用户在使用共享资源之前很有可能不知道资源的确切位 置，或者用户希望选择在当前环境下最优的、最适合自己的资源，这就需要动态 地根据当时的系统状况进行资源查找。快速地找到满足用户需求的资源，是用户 能够直接感知的系统体验。而为用户找到最优的满足条件的资源，对用户及后续 资源的使用有很大的影响。所以，无论是从性能上，还是功能上，资源发现都是 用户非常关注的服务。 2 、资源发现是众多应用的基石。 网络越来越成为人们生活的一部分，各种应用也层出不穷。而资源发现是一 个基础，能够为很多上层的应用提供服务，是众多上层应用的基石。 3 、资源发现可以为资源调度，资源使用收费等提供实现的手段和有力的支 持。 1 2 国内外研究现状 当前的一些广域分布式系统，对研究网格资源发现模型有很好的借鉴意义： g l o b u s 计算网格中的m d s 实现了基于l d a p 的树状元数据目录服务； m a t c h m a k e r i s 】不依赖全局资源命名，单依赖属性匹配的集中式资源共享系统； w | e b 服务中的u d d l l 6 1 实现了集中式服务实体的统一描述、注册和查找；中科院 的织女星网格基于资源路由器【7 】的资源发现机制。p 2 p 环境中采用了一些分布式 资源定位方法【8 】。然而，这些方法存在一定的不足。完全集中式的资源查找效率 高，但可靠性很差，存在单点失效问题，可扩展性比较差，受限于中央信息节点 的能力，不适合于大规模系统；完全分布式方法中资源信息空间的无序性和无结 构性使得资源发现具有一定的盲目性，基于洪泛或广播的资源发现效率较低。路 由器的资源发现机制具有灵活性不高，性能不够好等缺点。现有很多研究成果 9 1 2 浙江工业大学硕士学位论文 将p 2 p 资源发现方法应用到网格资源发现中，较好的方法是结构化p 2 p ，其资源 定位策略在定位性能、分布式控制和可扩展性等方面都有一定的优势，但结构化 p 2 p 需要维护d h t ( d i s t r i b u t e dh a s ht a b l e ) ，维护代价高，不适用于动态变化的网 格环境。 当前大部分对网格资源匹配的研究都要求用户请求的资源和资源提供者提 供的资源之间实现精确匹配。但是，这种机制限制太大【l o l ，因为在现实世界中， 人们在对某个事物或事件进行判断、推理、预测、决策时，所面对的信息常常是 不精确的、不完全或模糊的，人们事前无法准确预测资源的种类和数量。因此非 常需要高效的基于模糊匹配的资源发现方法根据用户的需求和满意度来灵活地 发现资源【l 。而且现有研究在无法找到满足用户需要的资源时，主要是简单地返 回给用户查找失败的消息。但在实际情况中，很多用户对请求的资源存在协商的 余地。 针对当前研究存在的问题，本文通过在g n u t e l l a 模型基础上进行改进，并 引入协商机制，得到能够支持基于v a g u e 集的模糊匹配机制的m s r 三层资源发 现模型，该模型的资源发现性能比g n u t e l l a 模型有大幅度地提升。此外，为了鼓 励更多的优质资源节点加入网格和防止恶意资源节点擅自夸大自己的能力，本文 采用了v a g u e 集表示的信用度来描述资源节点的信誉，并引入了相应的激励机制 和惩罚机制来保障模型高效地运行。 1 3 论文内容和组织结构 本文首先介绍了f u z z y 集、r o u g h 集和v a g u e 集三种研究信息系统中知识不 完全、不确定问题的重要方法，并简单阐述了f u z z y 集、r o u g h 集和v a g u e 集的 相关研究及应用。接着详细介绍非结构化p 2 p 和结构化p 2 p 两种网格资源发现 模型，在分析两种模型存在的问题的基础上，对g n u t e l l a 模型进行改进得到能够 支持基于v a g u e 集的模糊匹配机制的资源发现模型m s r 三层资源发现模型。 然后提出了基于v a g u e 集的资源匹配算法，并结合m s r 三层资源发现模型进行 了模糊匹配实验和跟g n u t e l l a 模型的对比实验。最后针对目前区分服务中现有激 励机制主要通过简单的整数值来描述这些模糊的衡量指标的局限性，本文提出了 基于v a g u e 集的激励机制和惩罚机制。本文还将基于v a g u e 集的激励机制和惩罚 浙江工业大学硕士学位论文 机制引入到资源匹配中，对基于v a g u e 集的资源匹配算法做进一步改进，并对改 进后的资源匹配算法进行了仿真实验。 论文内容具体组织如下： 第一章介绍了本文研究的背景知识和研究意义；然后简述了国内外的研究现 状；最后，给出了本文的研究内容和论文的结构组织。 第二章依次介绍f u z z y 集、r o u g h 集和v a g u e 集的基本概念和各自的相关研 究及应用。 第三章首先介绍非结构化p 2 p 和结构化p 2 p 两种网格资源发现模型，在分 析两种模型存在的问题的基础上，对g n u t e l l a 模型进行改进，得到能够支持基于 v a g u e 集的模糊匹配机制的m s r 三层资源发现模型。 第四章提出了基于v a g u e 集的资源匹配算法，并结合m s r 三层资源发现模 型进行了模糊匹配实验和跟g n u t e l l a 模型的对比实验。 第五章介绍了当前p 2 p 网络存在的货币激励和区分服务两类激励机制后， 提出了基于v a g u e 集的激励机制和惩罚机制，并将基于v a g u e 集的激励机制和惩 罚机制引入到资源匹配过程，使得基于v a g u e 集的资源匹配算法进一步改进，并 对改进后的资源匹配算法进行了仿真实验。 第六章总结了本文在基于v a g u e 集的网格资源发现模型中的研究成果，指出 了改进后的模型和算法还存在的不足和缺陷，并对网格资源发现模型的发展进行 了展望。 最后附上参考文献和致谢。 1 4 本章小结 本章作为本文的绪论，首先介绍了本项研究的背景：网格和资源发现的概念 和意义；接着，重点介绍了目前国内外在资源发现方面的研究进展情况；然后对 本文的研究内容进行了阐述，突出了本文所研究的三个方面的重要意义；最后， 介绍了本文的组织结构。 4 浙江工业大学硕士学位论文 第2 章处理不确定信息的理论方法 f u z z y 集、r o u g h 集和v a g u e 集是最常用的研究信息系统中知识不完全、不 确定问题的重要方法，它们各自有其优势和特点，并且在计算机科学及应用的多 种领域中有着重要的实际应用。本章将依次介绍f u z z y 集、r o u g h 集和v a g u e 集 的基本概念和它们的相关研究及应用。 2 1f u z z y 集 2 。1 1 基本概念 在自然科学或社会科学研究中，存在许多定义不很严格或者说具有模糊性的 概念。在集合论中，对于论域中的任何一个对象，它与集合之间的关系只能是属 于或者不属于的关系。然后随着科学技术的飞速发展，集合论在表示和处理各种 “亦此亦彼 的模糊性事物时显得力不从心。为了能够更好地处理具有上述特征 的信息，l a z a d e h 于1 9 6 5 年创立了f u z z y 集理论【1 2 1 ，用精确的数学语言对模 糊性进行描述。 定义1 【1 2 】设u 是一个论域，对u 的任一元素u ，u 中的一个f u z z y 集f 用 一个隶属函数f ：t 一l - o ，1 】表示，设甜u ，则所0 ) 表示甜属于f 的程度，称作0 ) 为“关于f u z z y 集f 的隶属度，简记为t f 。 当f 0 ) = l 时，材完全属于f ； 当f 0 ) = o 时，甜完全不属于f ； 当o 所 ) 1 时，“在f 0 ) 的程度上属于死 这样，对于论域u 上的一个对象“和u 上的一个f u z z y 集f ，不能简单地 说“具有还是不具有集合f 所代表的性质，只能说u 在多大程度上属于集合f ， 5 浙江工业大学硕士学位论文 f 0 ) 正是属于集合f 的程度的度量。 定义2 【1 2 】设彳和曰为论域u 的两个f u z z y 集，隶属函数分别为1 月0 ) 和 鳓0 ) ，则f u z z y 集合a 和b 的并集彳u 召、交集彳厂、b 和补集彳的运算可由它 们的隶属函数来定义。 ( 1 ) 并集 _ u 曰0 ) = 心0 ) v 鳓0 ) ，其中v 表示取二者中的较大值。 ( 2 ) 交集 心n 曰g ) = 儿0 ) 人心0 ) ，其中 表示取二者中的较小值。 ( 3 ) 补集 。a c 0 ) = l 一儿0 ) 现实生活中很多事物之间是不能完全分开的，通常都存在着亦此亦彼的情 况。因此，f u z z y 集的产生，为处理模糊和不确定性信息提供了一个强有力的工 具，从此可以用结构化和公式化的数学手段处理边界不确定信息，从而在模糊环 境中做出正确的决策。事实上，人类的大脑正是基于模糊规则进行判断，推理和 决策的。 2 1 2 相关研究及应用 f u z z ) ，集理论目前正沿着理论研究和应用研究两个方向迅速发展着。理论研 究主要是经典数学概念的模糊化。由于模糊集自身的层次结构，使得这种理论研 究更加复杂。目前已形成了模糊拓扑、模糊代数、模糊分析、模糊测度及模糊计 算机等模糊数学分支。 在应用研究方面，近年来一些学者将f u z z y 集理论引入到图像处理中，取得 了不错的效果，如沈桂玲等【1 3 1 将f u z z y 集理论应用于图像分割。还有一些学者将 f u z z y 集应用在w e b 日志挖掘【1 4 1 和近似推理【1 5 1 。 随着网格技术地不断发展，国内很多学者开始将f u z z ) ，集应用在网格方面， 唐文等【1 6 】结合f u z z y 集合理论来研究主观信任管理模型，开辟了信任模型研究的 新思路。高承实等【l7 j 从网格的结构特点出发，针对行为信任的模糊性，运用f u z z y 6 浙江工业大学硕士学位论文 集合理论构造了一个完整的网格环境下的动态行为信任评估模型，以此来建立、 管理和评估网格实体间的信任关系。桂劲松等【1 8 】考虑网格实体身份的不确定性， 研究了f u z z y 集理论在行为信任模型中的应用。文献【1 9 】中考虑到信任的动态性， 结合时间衰减和路径衰减两个因素，提出了一种基于f u z z y 集合的信任更新模 型。王墙等【2 0 】提出了f u z z y 集下q o s 感知的网格服务优选算法。 以上所述的内容只占f u z z y 集应用范围的很少部分，f u z z y 集的应用范围已 遍及自然科学与社会科学的几乎所有的领域，特别是在模糊控制、模式识别、聚 类分析、系统评价、数据库、系统决策、人工智能及信息处理等方面取得了显著 成就。 2 2r o u g h 集 2 2 1 基本概念 r o u g h 集理论是2 0 世纪8 0 年代初由波兰数学家z p a w l a k 首先提出的处理 不确定知识的数学理论，它能有效的分析和处理不精确、不一致、不完整等各种 不完备信息，并从中发现隐含的知识，揭示潜在的规律【2 l 】。 r o u g h 集理论是以不可分辨关系划分所研究论域的知识，形成知识表达系 统，利用上、下近似集逼近描述对象，通过知识约简，从而获得最简知识，下面 介绍其基本概念【2 2 】。 1 ) 知识、分类及不可分辨关系 r o u g h 集理论是以知识、分类为基础的，知识是基于对对象进行分类的能力， 由分类模式组成。利用不同的属性知识描述，可以产生不同的分类。分类主要用 来产生范畴，这些范畴构成知识模块，即分类的类。 不可分辨关系是r o u g h 集理论的基础。论域u 中的一些元素可能均与相同 的若干信息存在联系，这些元素间有着一种不可分辨的关系。换言之，u 中的一 些对象具有若干相同的属性值，因此，仅通过这些属性值是无法区分它们的，从 这个角度看，它们是不可分辨的【2 3 1 。对于给定属性集r a ，则可以构成一个二 元等价关系r ，它满足f 耐取) = 戤，x ，) uiv a r ，厂g ，口) = b ，口) j 。 从上述定义看出，如果b ，x ，) i n d ( r ) ，那么对于t 和x ，是不能被r 中的属 7 浙江工业大学硕士学位论文 性所分辨的。 2 ) 边界与粗糙度 r o u g h 集理论中的不确定性和模糊性是一种基于边界的概念，即一个模糊的 概念具有模糊的边界。每一个不确定概念由一对称为上近似和下近似的精确概念 来表示：设给定k = p ，r ) ，对于每个子集x u 和一个等价关系r 切d 伍) ， 可以根据r 的基本集合描述来划分集合五 月伍) = y 口u riyc 7 x 尺一伍) = y 口u rl 】，ix ) 式中，r 一伍) 和欠一伍) 分别称为x 的r 下近似和r 上近似。 集合砌r 伍) = r 一似) 一r 一伍) 称为x 的边界域；p o s r 似) = 尺一伍) 称为x 的 r 正域；n e g r 伍) = u r 一伍) 称为x 的r 负域2 4 1 。 r 一( ，) 是由那些根据知识r 判断可能属于x 的元素组成的集合；r 一( ) 是 由那些根据知识r 判断可能属于x 的元素组成的集合；b n r 伍) 是由那些根据指 示r 判断可能属于x 又可能属于u x 的元素组成的集合；n e g r ( ) 是由那些根 据知识r 的判断肯定不属于x 的元素组成的集合。论域种等于某个等价类或某 些等价类的并集的集合称之为可定义集( 精确集) ，反之称为不可定义集，也称 r o u g h 集。 集合的不确定性是由边界域的存在造成的，由等价关系r 定义这种不确定 程度( 粗糙度) 。c a r d ( * ) 表示集合元素数，且x ： 删小舞c a r a 嘲 协， l “i a j 3 ) 知识表达系统 在r o u g h 集理论中，对象的知识是通过指定对象的基本特征( 属性) 和它 们的特征值( 属性值) 来描述的。一个知识表达系统定义为s = 妙，a ，眈) ，口) ， 其中，u 为非空有限集，称论域；a 为非空有限集，称属性集合；圪为属性a a 的值域：口：”圪为一单射，使论域u 中任一元素取属性口在圪中的某一唯一 8 浙江工业大学硕士学位论文 值。如果么由条件属性集合c 和结论属性d 组成，c 、d 满足cy d = a ，cid = ， 则称s 为决策系统。 4 ) 知识约简与核 r o u g h 集理论在知识表达系统的基础上定义了约简与核这两个非常重要的 概念，进而提供了分析多余属性的方法，对知识的处理是通过对决策表中的属性 值的处理实现的。一般通过先删除重复的实例及多余的属性，对每个实例删除多 余的属性值，然后求出最小约简，并根据最小约简，求出逻辑规则。 综上所述，r o u g h 集理论的基本框架可归纳为：以不可分辨关系划分所研究 论域的知识，形成知识表达系统，利用上、下近似集逼近描述对象，通过知识简 约获得最简知识。 2 2 2 相关研究及应用 r o u g h 集虽然是近2 0 多年才逐渐发展起来的，但自它问世以后，无论在理 论上还是实际应用上都有迅速地发展。 在理论方面，对p a w l a k 粗糙模型的推广一直是r o u g h 集理论研究的主流方 向，主要包含两种方法：构造性方法和代数方法。 构造性方法是对p a w l a k 粗糙集模型的一般推广，其主要思路是从给定的近 似空间出发去研究粗糙集合近似算子。相关研究成果如基于邻域算子的r o u g h 集模型【2 5 】，统计r o u g h 集模型1 2 6 ，2 7 2 引，变精度r o u g h 集模型【2 明等。 代数方法由于应用性不够强，目前关于代数方法的r o u g h 集理论研究大多局 限于经典集情况，对于模糊集情况虽有讨论【3 0 】，但比较少。 r o u g h 集在应用研究方面也取得很多成果。如文献 31 1 应用r o u g h 集方法分 析十年间股票的历史数据，研究股票价格和经济指数之间的关系。文献 3 2 1 应用 r o u g h 集方法研究手写字符识别问题，提取了特征属性。r o u g h 集还被应用于从 数据库中知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) t 3 3 , 3 4 。r o u g h 集在医疗 诊断上也有所应用，r o u g h 集方法根据以往的病例归纳出诊断规则，指导新的病 例，如通过r o u g h 集方法预测早产可把准确率从1 7 3 8 提高到6 8 9 0 3 5 】。 以上只是r o u g h 集研究和应用的很小部分，r o u g h 集在机器学习、知识获取、 决策分析、专家系统、归纳推理、模糊控制等很多领域都已经有所研究。 9 浙江工业大学硕士学位论文 2 3v a g u e 集 2 3 1 基本概念 g a u 和b u e h r e r 于1 9 9 3 年提出了v a g u e 集合理论【3 6 1 ，弥补了传统f u z z y 集 合理论的缺陷。f u z z y 集理论虽然能够较好地描述模糊性，它采用单值的隶属函 数表示“一定程度上属于 的关系，即单值的隶属度包含了支持和反对证据的程 度，但它不能表示中立( 既不支持又不反对) 的证据。v a g u e 集合解决了f u z z y 集 合存在的问题。在v a g u e 集中，给每个对象同样分派一个隶属度，不同的是该隶 属度是【0 ，1 的一个子区间，这个子区间既给出了支持x 彳的证据，同时也给出 了反对x x 的证据，比f u z z y 集更好和更准确地表达模糊信息。下面介绍v a g u e 集的定义。 定义3 ( 3 r l 设石是一个对象空间，其中的任意一个元素用x 表示，x 中的一 个v a g u e 集y 用一个真隶属函数r ，和一个假隶属函数六表示。t v b ) 是从支持x 的证据所导出的x 的肯定隶属度下界，z g ) 则是从反对x 的证据所导出的x 的 否定隶属度下界，r ，g ) 和 g ) 将区间【o ，1 】中的一个实数与x 中的每一个点联 系起来，i 1 t ，g ) ：x 专 o ，l 】，工g ) ：x 【o ，l 】；其中，g ) + 兀g ) 1 。 设v 为一v a g u e 集，当x 是连续的时候，有： v = ( x ) ，1 一 ( x ) x d x ，z x ( 2 - 2 ) e 当x 是离散的时候，有： y = 【，( x 。) ，1 - f , ( x ，) 】而，t j ( 2 - 3 ) 由上述定义可知，f ，g ) 是v a g u e 集的真隶属函数，表示支持x 的证据的必 要程度；工b ) 是v a g u e 集的假隶属函数，表示反对x 的证据的必要程度；1 一工g ) 表示了支持x x 的证据的可能程度，而1 一，g ) 一工g ) 则表示了关于x 的不确定 性。 v a g u e 集中，当1 一工g ) = f ，g ) 时，则可以精确地知道x , v a g u e 集退化为模糊 集；当l 一工g ) 和，g ) 都同时为1 或0 时，v a g u e 集退化为经典集合。 i o 浙江工业大学硕士学位论文 定义4 3 7 ：设t l 是一t 范数，其相应的t 余范数为上l ，两个v a g u e 集a 和b 的并集是v a g u e 集c ，即c = a y b ，其真假隶属函数分别为： f 。= ，_ v t b ，l 一无= ( 1 一无) 上。( 1 一厶) 定义5 【3 7 】：设t l 是一t 范数，其相应的t 余范数为”，两个v a g u e 集a 和b 的交集是v a g u e 集c ，即c = a ib ，其真假隶属函数分别为： t c = f t l t b ，1 一丘= ( 1 一厶) ( 1 一厶) 其中，“v ”和“八”分别为取大和取小算子。在实际应用中，由于t 范数可选， 从而使这种新的定义具有更好的灵活性。在本模型中 - r l ”和“上l 分别取“代 数积”和“代数和”，即a t l b = a b ，a _ li b = - a + b a b 。 定义6 【3 7 】：v a g u e 集a 为b 所包含，即a c _ b ，当且仅当s t 口，1 f a _ 1 厶。 2 3 2 相关研究及应用 在应用方面，台湾学者s m c h e n 将v a g u e 集应用在模糊决策系统中，并提出 了v a g u e 集的相似度量概念【3 8 】，而有关基于v a g u e 集的模糊信息处理方面的研究 尚处于起步。相对于v a g u e 集而言，国内外研究f u z z y 集和区间值集的时间较长， 在1 9 9 6 年，西班牙学者h b u s t i n c e 指出v a g u e 集在某种程度上也可以用直觉模糊集 来表示【3 9 】。这表g j v a g u e 集、f u z z y 集、直觉模糊集、区间值集之间有很深的内在 联系，我们也可借助这一点来发展v a g u e 集理论及其在模糊信息处理中的应用。 另外，一些学者将v a g u e 集应用到近似推理领域，可看作是模糊推理的一种延伸， 如：李凡等【4 0 i t ，采用基于v a g u e 集的插值方法进行近似推理，其结果比文献【4 1 】 基于相似度量的模糊推理方法更精确、可信，更符合人们的直觉；文献 4 2 1 针对 在智能系统中实现基于v a g u e 集的近似推理，提出了一类蕴涵算子。后来近似推 理由单向发展到双向推理，如王天江等【4 3 j 提出基于v a g u e 集加权相似度量的双向 近似推理方法。v a g u e 集应用于近似推理不仅仅在国内，在国外也有，如c a s t i l l o 等【删认为v a g u e 集推理近似等于两个模糊推理之和。而且，一些学者利用这个思 想将v a g u e 集应用到电厂监控，使得监控过程计算简单，同时又能充分利用v a g u e 集的优点，因此取得了相当好的效果 4 s l 。 除了上述两个主要的应用领域外，v a g u e 集在其它领域也有应用，如 浙江工业大学硕士学位论文 d e k u m a r 等f 删通过定义v a g u e 集的模糊关系及其模糊关系的合成，将其应用在 医疗诊断中，为建立医疗诊断专家系统奠定了基础。c h e n 【4 7 1 利用v a g u e 集理论 分别对串联、并联的模糊系统的可靠性进行分析，整个过程简单、条理清楚。 2 4 本章小结 本章依次介绍了三种研究信息系统中知识不完全、不确定问题的重要方法： f u z z y 集、r o u g h 集和v a g u e 集，并简单论述了它们的相关研究及应用。f u z z y 集、r o u g h 集和v a g u e 集研究问题的着眼点是不同的，同时，它们又可以相互结 合，以发挥各自的优势。 1 2 浙江工业大学硕士学位论文 第3 章p 2 p 网格资源发现模型 在本章里，首先介绍两种不同的p 2 p 资源发现模型( 非结构化和结构化) ， 并根据它们的性能和能力进行比较。然后详细介绍采用非结构化p 2 p 资源发现 方法和结构化p 2 p 资源发现方法的网格系统。最后本文在分析两种模型存在的 问题的基础上，对c m u t e l l a 模型进行改进得到能够支持基于v a g u e 集的模糊匹配 机制的资源发现模型m s r 三层资源发现模型。 3 1p 2 p 系统中的资源发现方法 3 1 1 非结构化p 2 p 系统 1 9 9 9 年提出的n a p s t e r 是历史上第一个p 2 p 系统。它包含一台中央服务器， 这台服务器储存系统中其它节点共享的所有文件的索引。用户在查找文件时，向 中央服务器发送文件的名字，服务器返回给用户包含该文件的节点的i p 地址， 然后请求节点和文件所在节点之间建立直接的连接。n a p s t e r 中的中央索引服务 器不适合大规模使用，容易单点失效。尽管n a p s t e r 在历史上被认为是第一个非 结构化的p 2 p 系统，但是由于中央索引服务器的存在，使得它较大地区别于现 在的非结构化p 2 p 系统。 在当今的非结构化p 2 p 系统中，每个节点和其它节点维持一定数量的连接， 这些相邻的节点被成为邻居节点，因此节点覆盖网络便形成了。g n u t e l l a 和k a z a a 被认为是两个最流行的非结构化系统( 图3 1 ) 4 8 】。 浙江工业大学硕士学位论文 图3 1g n u t e l l a 结构 由于这些系统缺乏基本的结构，无法知道文件的位置，因此流行的资源发现 方法是“洪泛 。一个节点为了查找一个文件，发出一个查询请求，该请求在网 络内进行广播。所有匹配查询请求的响应通过反向路径发回给源节点。显然，洪 泛不适合大规模系统，因为它产生大量不必要的网络流量。为了限制洪泛产生的 消息数量，每个消息被加上一个t t l ( t i m e t o l i v e ) 字段。t t l 表明消息从源 节点开始，它能传播的跳数。1 i ，i - l 太小会减小网络的覆盖率，因此会出现一个文 件虽然存在于系统中，但是却无法找到。 为了限制洪泛产生的巨大的消息量，当今非结构化p 2 p 系统采用了可控的洪 泛机制，也就是众所周知的动态查询m 9 1 。在动态查询中，源节点在一个小的t t l 下，把请求发送给它的一个邻居子集。如果第一次尝试不能产生足够的结果，源 节点在增加的t t l 下，把请求发给和之前不同的邻居子集。这个过程被重复进行， 直到找到满意数量的结果，或者直到所有的邻居都找光。很多其它技术已经被提 出来去减轻由于洪泛引起的拥塞问题【5 0 】和处理拥塞及覆盖率的平衡5 1 1 ，比如 r a n d o mw a l k s ，多重r a n d o mw a l k s ，结合洪泛和r a n d