（计算机应用技术专业论文）分布式协作环境中的信任关系动态性研究.pdf

善 、 o t - 独创性声明 i i l lllri i ii fi i i i i i iiii y 17 8 916 4 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：牟缝一日期：丑吐坦l 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：玉p 趾导师签名： 一一 摘要 摘要 随着资源的爆炸式增长，分布式协作对p 2 p 下载、g r i d 计算、互联网搜索、 云计算等实际应用的意义越来越重要。复杂网络学科的兴起为研究p 2 p 网络、 g r i d 、i n t e r n e t 等分布式协作环境提供了一种新的思路，即将它们映射成面向信 息共享等服务的复杂网络，简称为服务网络。服务网络由很多个相对独立的实 体组成，并呈现大规模、开放、时时动态变化、分布式等特征，即：网络实体 数目巨大、实体随时可以离开或加入网络、实体间的连接不断变动、网络缺乏 中枢控制等等。这些特征对研究服务网络实体协作和伙伴搜寻研究提出了重重 挑战。此外，服务网络复杂性的另一体现，即实体的微观交互和宏观网络特征 的相互影响和作用机制，也是研究人员需要解决的一大问题。虽然人们已经意 识到信任关系能帮助实体从海量对象中挖掘出特定目标，但它本身的不确定性、 模糊性、动态性等固有特征，使它无法在现实服务网络得到广泛应用。 为了促进信任关系在伙伴搜寻和服务网络中的应用，本文引入了基于面向 自治的计算范式( a u t o n o m y o r i e n t e dc o m p u t i n g ，a o c ) 。a o c 通过定义实体简 单特征、交互行为和规则，刻画复杂网络特征，挖掘造成这些特征出现的潜在 机制。自治和自组织是a o c 的两大核心思想。自治，指实体自我管理的能力， 即实体根据自身状态以及周围环境状态决定当前的行为；自组织，则是指通过 实现正反馈等机制实现实体状态及其环境状态的更新，并基于更新后的状态指 导未来行为。 具体来说，针对伙伴搜寻问题，本文尝试基于a o c 刻画服务网络和信任关 系的动态性，挖掘信任关系及其动态性对实体和服务网络的影响机制。具体工 作介绍如下： 第一，提出基于信任关系的伙伴选择策略，并通过分析其在服务网络中的 应用结果，首次系统地分析了信任关系对服务网络和实体的影响。在张世武等 人所提的服务网络模型基础上，提出了基于信任关系的伙伴选择策略。在不同 结构网络中，即在随机网络、小世界网络和无标度网络中，测试比较了基于信 任关系的伙伴选择策略、随机选择策略和基于伙伴关系的策略对实体特性、网 北京工业大学 ：学博七学位论文 络结构和网络服务性能的不同影响。实验结果表明，在任何一种服务网络中， 信任关系都能大幅度提高实体协作完成服务需求的概率，提高服务网络性能。 同时，实验结果表明，采用基于信任关系的策略，实体在经过较短时间的交互 后能找到相对合适的伙伴，为成功完成新需求创造条件。 第二，首次从复杂网络角度刻画了信任关系的动态性，提出了面向自治伙 伴搜寻的动态信任网络模型，探讨了信任关系动态性对网络和实体的影响机制。 首先，基于a o c 的核心思想：自治和自组织，构建了一个动态信任网络模型。 网络中的实体将根据自身能力、收到的服务需求以及当前信任关系等信息选择 当前的伙伴搜索和选择操作，并根据伙伴反馈信息创建、更改、删除彼此的信 任关系。其次，基于完成不同需求的一系列实验，用网络结构特征的动态变化 展示了信任关系和服务网络的动态性。再次，通过分析信任关系变化及其对应 的实体连接、网络结构和网络性能等因素的变化，发现：实体通过改变彼此间 的信任关系，改变网络整体结构；改变后的网络结构，能使实体尽快找到伙伴； 而信任关系本身的定义，决定了找到的伙伴能以较高的概率成功完成需求，最 终使服务网络的整体性能得到了提升。 第三，针对多伙伴搜寻问题，提出了一种面向自治的、基于信任关系的分 布式协作搜寻策略。前两项工作中的策略、行为和规则，都是为搜索一个伙伴 服务的。而在现实情况中，经常遇到需要多个实体一起工作的情况。因此，针 对多目标搜寻问题提出分布式协作策略是非常必要的。本文分布式协作策略的 核心依然是自治，即实体根据自身的服务能力、它所收到的服务需求、完成此 需求能获得的收益，以及当前对其他实体的信任关系等因素决定它是否进行搜 寻，如何搜寻。对照现实世界，在实现实体自治和利益驱动的行为模式基础上， 定义了四种行为：泛洪搜寻、基于信任关系的搜寻、空搜寻和随机搜寻。实验 结果证实了此分布式协作搜寻策略在上述信任网络中的有效性和鲁棒性。 综上所述，本文基于面向自治的计算范式，通过在协作伙伴搜寻环节引入 信任关系，系统分析了信任关系对服务网络和实体的影响，并尝试刻画了服务 网络中信任关系的动态性，挖掘此动态性对服务网络和实体的影响机制。最后， 提出了一种面向自治的分布式搜寻策略，促进服务网络中基于信任关系的协作。 关键词动态性；信任关系；伙伴搜寻；面向自治的计算；服务网络 a b s t r a c t a b s t r a c t d i s t r i b u t e dc o l l a b o r a t i o nb e c o m e sm o r ep o p u l a ra n di m p o r t a n tf o ro p e n ， d i s t r i b u t e ds e r v i c e o r i e n t e dn e t w o r k sf o rs u c ht a s k s a s f i l e - s h a r i n g ，r e s o u r c e a l l o c a t i o n ，e t c r e s e a r c ho nc o m p l e xn e t w o r k sa c c e l e r a t e ss t u d y i n gs u c hn e t w o r k s t h r o u g hm o d e l i n gt h e ma ss e r v i c en e t w o r k s ，w h i c h c o n t a i nag r e a ta m o t m to f i n d e p e n d e n te n t i t i e s ( a g e n t s ) a sn o d e sa n dt h e i rc o u p l i n gr e l a t i o n s h i p sa sl i n k s t h o s ee n t i t i e sw o r kt o g e t h e rf o rp r o v i d i n gv a r i o u ss e r v i c e s ，s u c ha sd e l i v e r i n g m e s s a g e i n f o r m a t i o n ，t r a n s p o r t i n ga n dc o m m u n i c a t i n g t h o s en e t w o r k s a r er e a l l y l a r g e s c a l e ，o p e n ，d y n a m i ca n dd i s t r i b u t e d ，t h u sc o o p e r a t i o n r e l a t e di s s u e s ，s u c ha s h o we n t i t i e sw o r kt o g e t h e r , b e c o m eb i gc h a l l e n g e sn o w a d a y s h e r e ，w ef o c u so nt h e p r o b l e mo ff i n d i n gp a r t n e r s ，i e ，t oi d e n t i f yw h i c he n t i t i e sc a np r o v i d er e q u e s t e d s e r v i c e sf r o mag r o u po fe n t i t i e s p r e v i o u ss t u d i e sh a v es h o w nt h a te n t i t i e sc a nr e f i n e a n dd e t e r m i n ep a r t n e r st h r o u g hm e a s u r i n gt r u s tr e l a t i o n s h i p s ，i e ，t h eb e l i e f so f e n t i t i e st h a to t h e r sw i l la c c o m p l i s har e q u e s tf o ra s s i g n e ds e r v i c e sa th a n d h o w e v e r , t h ea p p l i c a t i o n 、o ft r u s tr e l a t i o n s h i p si nf i n d i n gp a r t n e r si sr e s t r i c t e dd u et ot h e i r u n c e r t a i n t y , d y n a m i c si n t r i n s i cc h a r a c t e r i s t i c s h e r e d y n a m i c sr e f e rt ot h a te n t i t i e s d y n a m i c a l l yc h a n g et h e i rb e l i e f st h r o u g hr e c a l l i n gt h e i rp a s te x p e r i e n c e si no r d e rt o q u i c k l yi d e n t i f yp a r t n e r sf o rn e wr e q u e s t s e n d e a v o r i n gt oa d v a n c et h ea p p l i c a t i o n so ft r u s tr e l a t i o n s h i p si nf i n d i n gp a r t n e r s i ns e r v i c en e t w o r k s ，w ea i mt oc h a r a c t e r i z et h ed y n a m i c so ft r u s tr e l a t i o n s h i p sa n di t s e f f e c t so ne n t i t i e sa n ds e r v i c en e t w o r k s ，d i s c o v e rc o r r e s p o n d i n gu n d e r l y i n g m e c h a n i s m s t ot h o s ee n d s ，w ei n t r o d u c eab o t t o m - u pc o m p u t i n gp a r a d i g m ，i e ， a u t o n o m y o r i e n t e dc o m p u t i n g ( a o c ) ，w h i c hc a nh e l p u sc h a r a c t e r i z ec o m p l e x f e a t u r e so rp h e n o m e n aa n du n d e r s t a n dh o wt h e ye m e r g ef r o ml o c a lb e h a v i o r s ，b a s e d o nd e f i n i n gr e l a t i v e l y - s i m p l ee n t i t i e s s t a t e s ，b e h a v i o r a lr u l e sa n db e h a v i o r s ，c o u p l i n g r e l a t i o n s h i p sa n ds oo n t h ec o r ei d e a so fa o c a r ea u t o n o m ya n ds e l f - o r g a n i z a t i o n a u t o n o m yr e f e r s t ot h a te n t i t i e sc a ni n d e p e n d e n t l yd e t e r m i n et oa c t i v a t ew h i c h b e h a v i o r sb a s e do ne v a l u a t i n gt h e i rs t a t e s ，c o u p l i n gr e l a t i o n s h i p sa n ds o o n s e l f - o r g a n i z a t i o n d e n o t e st h a t e n t i t i e s s t a t e s ，c o u p l i n gr e l a t i o n s h i p s a n do t h e r c h a r a c t e r i s t i c sa r ed y n a m i c a l l yc h a n g i n gw h i l et h ew h o l en e t w o r kc o n v e r g e st oi t s t a r g e ts t a t e t or e a l i z es e l f - o r g a n i z e dc o m p u t i n g ，e n t i t i e sm u s th a v et h ec a p a b i l i t i e so f r e c e i v i n ga n ds e n d i n gi n f o r m a t i o nt ot h e m s e l v e sa n dt h e i re n v i r o n m e n t s ，a n dt h e n t h e yc a nd e c i d ew h a tt od on e x ta n df e e d b a c kc o r r e s p o n d i n g r e s u l t s o u rc o n t r i b u t i o n sa r es p e c i f i e da sf o l l o w s ： f i r s t l y , w es y s t e m a t i c a l l yq u a n t i f yt h ee f f e c t so ft r u s tr e l a t i o n s h i p so ne n t i t i e s p r o f i l e s ，t h es t r u c t u r a lc h a r a c t e r i s t i c so fs e r v i c en e t w o r k sa n dt h e i re f f i c i e n c yi n p r o v i d i n gs e r v i c e s s p e c i a l l y , w ei n t r o d u c eap a r t n e rs e l e c t i o ns t r a t e g yb a s e do nt r u s t i i i r e l a t i o n s h i p si n t oa l le x i s t i n gm o d e lo fs e r v i c en e t w o r k s e x p e r i m e n t a lr e s u l t sh a v e s h o w nt h a tt h en e t w o r kw i t ht h i ss t r a t e g yc a na c c o m p l i s hv a r i o u ss e r v i c e s 、l ma h i g h e rp r o b a b i l i t y , c o m p a r i n gt o t h a tw i t hr a n d o ms t r a t e g yo rp a r t n e r s h i p b a s e d s t r a t e g y m o r e o v e r , t h es t r a t e g yb a s e do nt r u s tr e l a t i o n s h i p sc a t lm a k et h en e t w o r k q u i c k l yc o n v e r g e t oi t s e q u i l i b r i u m s t a t e ，i e ，t h e v a l u e so fi t ss t r u c t u r a l c h a r a c t e r i s t i c sr e m a i ns t a b l e s e c o n d l y , w ep r o p o s ead y n a m i cn e t w o r ko ft r u s t b a s e de n t i t i e s ，i e ，ad y n a m i c t r l l s tn e t w o r k ，c h a r a c t e r i z et h ed y n a m i c so ft r u s tr e l a t i o n s h i p sb ym e a no fe x a m i n i n g t h ed y n a m i c so fi t sn e t w o r ks t r u c t u r e ，a n dd i s c o v e rt h ee f f e c t so f t h i sd y n a m i c so n e n t i t i e s ，e f f i c i e n c y i n f i n d i n gp a r t n e r s a n dp r o v i d i n gs e r v i c e s s p e c i a l l y , t h e a b o v e m e n t i o n e dn o t i o no fa u t o n o m yi se m b o d i e di nd e f i n i n gh o w e n t i t i e sa c t i v a t e t h e i rp a r t n e rf i n d i n gb e h a v i o r s ，w h e r e a ss e l f - o r g a n i z a t i o ni sr e a l i z e dt ou p d a t et h e s t r e n g t ho ft r u s tr e l a t i o n s h i p s e x p e r i m e n t a l r e s u l t se x p l i c i t l yd i s p l a yad y n a m i c p r o c e s so ft h i sn e t w o r k ，c h a n g i n gf r o mc o n t a i n i n g n ol i n k ( t r u s tr e l a t i o n s h i p ) t o h a v i n gs o m es t a b l el i n k s f r o mt h e m ，w ec a nc o n c l u d e t h a tt h ec h a n g eo ft r u s t r e l a t i o n s h i p sa m o n ge n t i t i e sl e a d st ot h a to ft h et o p o l o g yo f aw h o l e n e t w o r k ，w h i l e t h o s ec h a n g e ds t r u c t u r a lc h a r a c t e r i s t i c sm a k ee n t i t i e sf i n d i n gp a r t n e r sm o r eq u i c k l y m o s ti m p o r t a n t l y , t h o s ef o u n dp a r t n e r sw i l ls u c c e s s f u l l yp r o v i d es e r v i c e w i t ha h i g h e rp r o b a b i l i t y , d u et ot h e d e f i n i t i o n o ft r u s t t h e r e f o r e ，t h ec h a n g eo ft r u s t r e l a t i o n s h i p sl e a d st o t h ee n h a n c e m e n to ft h ee f f i c i e n c yi nf i n d i n gp a r t n e r sa n d p r o v i d i n gs e r v i c e f i n a l l y , w ep r e s e n ta n e wd i s t r i b u t e dc o l l a b o r a t i v es t r a t e g yf o ra u t o n o m y 。o r i e n t e d f i n d i n gm u l t i p l ep a r t n e r s t or e a l i z et h ek e yi d e ao f a o c ，i e ，a u t o n o m y , w ed e p l o y f o u re n t i t i e s ，b e h a v i o r s ，i e ，f l o o d i n gf i n d i n g ，t r u s t - b a s e df i n d i n g ，n u l lf i n d i n ga n d r a n d o mf i n d i n g ，c o n s i d e r i n gt h ef a c tt h a tp r a c t i c a le n t i t i e sa r es e l f - i n t e r e s t e da n d 口r o f i t d r i v e n t h ee x p e r i m e n t a lr e s u l t sh a v ev a l i d a t e dt h ee f f i c i e n c ya n d r o b u s t n e s so f t h i ss t r a t e g yi nt h ea b o v e m e n t i o n e dt r u s tn e t w o r k i ns u m m a r y , r e s e a r c h e si nt h et h e s i si sb a s e do na u t o n o m y o r i e n t e dc o m p u t i n g a n df o c u so no b s e r v i n gt h ee f f e c t so ft r u s tr e l a t i o n s h i p sa n di t sd y n a m i c so ne n t i t i e s d r o f i l e s ，n e t w o r k s s t r u c t u r a lc h a r a c t e r i s t i c sa n dt h e i re f f i c i e n c yi nf i n d i n gp a r t n e r s a n dp r o v i d i n gs e r v i c e s ，w h i c hi sn e c e s s a r ya n di m p o r t a n t f o rd i s c o v e r i n gt h e w o r k i n g m e c h a n i s m so f t r u s t r e l a t i o n s h i p s f u r t h e r m o r e ，t h e d i s t r i b u t e d c o l l a l ：i o r a t i v es t r a t e g yc a nb eu s e da sr e f e r e n c ef o rt h er e s e a r c h e r s ，w h ow o r ko n p e r s o n a lr e c o m m e n d a t i o n ，c l o u dc o m p u t i n ga n do t h e rp r a c t i c a l i s s u e s k e y w o r d sd y n a m i c s ；t r u s tr e l a t i o n s h i p s ； c o m p u t i n g ；s e r v i c en e t w o r k s ； p a r m e rf i n d i n g ；a u t o n o m y o r i e n t e d 目录 目录 摘要i a b s t r a c t i i i 第1 章绪论l 1 1 课题背景“l 1 1 1 复杂网络”2 1 1 2 信任关系2 1 。2 本文主要研究内容”3 1 2 1 信任关系对服务网络和实体的影响3 1 2 2 信任关系动态性及其对服务网络和实体的影响机制4 1 2 3 基于信任关系的分布式协作搜寻策略4 1 3 研究意义”5 1 4 创新性工作”5 1 4 1 基于信任关系的伙伴选择策略及其影响分析6 1 4 2 信任关系动态性刻画及其影响机制分析6 1 4 3 面向自治的分布式协作搜寻策略7 1 5 本文结构8 第2 章复杂网络相关研究1 1 2 1 复杂网络简介l l 2 1 1 基本统计性质1 2 2 1 2 拓扑模型的构建1 4 2 1 3 分散式搜索策略1 5 2 2 复杂网络的动态性问题1 6 2 3 面向自治的计算”l7 2 3 1 面向自治的计算简介1 7 2 3 2a o c 与多a g e n t 技术的区别“1 7 2 3 3a o c 的建模方法1 9 2 3 4 基于a o c 方法的服务网络动态性研究2 0 2 4 本章小结2 l 第3 章分布式协作环境中的信任关系研究2 3 3 1 信任关系的定义”2 3 3 2 分布式评估模型2 4 3 2 1 代表性的评估模型”2 4 3 2 2 分布式评估需要解决的问题2 7 3 2 3 评估信息的选取2 8 3 2 4 评估模型的实用性分析2 9 3 3 信任关系动态性研究”3 1 3 4 基于信任关系的分布式搜寻”31 3 5 本章小结t 3 2 第4 章本文的研究范畴3 3 4 1 信任关系对服务网络影响的系统分析3 3 4 2 基于a o c 的信任网络模型构建和信任关系动态性刻画3 4 4 3 基于a o c 的分布式协作搜寻策略设计3 5 v 北京工业大学工学博+ 学位论文 4 4 本章小结3 5 第5 章信任关系对服务网络的影响研究3 7 5 1 服务网络3 7 5 1 1 实体3 7 5 1 2 服务需求3 8 5 1 3 服务流程3 8 5 2 信任关系3 9 5 2 1 相关定义“3 9 5 2 2 信任关系的评估”4 0 5 3 伙伴选择策略4 l 5 4 实验结果及分析4 l 5 4 1 实验设计和参数“4 1 5 4 2 服务网络性能“4 3 5 4 3 服务网络结构”4 5 5 4 4 信任关系动态性分析”5 l 5 5 本章小结5 2 第6 章面向自治伙伴搜寻的动态信任网络5 5 6 1 问题陈述5 5 6 2 面向自治伙伴搜寻的动态信任网络模型5 7 6 2 1 基本思想”5 7 6 2 2 实体的伙伴搜寻行为及规则5 9 6 2 3 信任关系及其更新机制6 1 6 2 4 需求匹配评估公式”6 4 6 2 5 面向自治的伙伴搜寻算法”6 4 6 3 实验结果及分析6 5 6 3 1 实验设计6 6 6 3 2 网络结构变化6 7 6 3 3 网络性能变化7 0 6 3 4 结构变化与性能变化之间的关系“7 2 6 4 鲁棒性验证7 3 6 4 1 固定的实体性能“7 4 6 4 2 自适应的实体性能”7 9 6 5 本章小结8 3 第7 章面向自治的分布式协作搜寻策略8 5 7 1 分布式协作搜寻问题8 5 7 2 面向自治的分布式协作搜寻策略8 6 7 2 1 基本思想8 6 7 2 2 解决协作搜寻问题的基本步骤”8 8 7 2 3 面向自治的搜寻行为及规则8 9 7 2 4 效益更新公式”9 1 7 2 5 面向自治的协作搜寻算法“9 2 7 3 实验结果及分析9 3 7 3 1 实验目的与设计”9 3 7 3 2 实验参数9 4 v i 目录 7 3 3 策略性能结果9 7 7 3 4 鲁棒性测试9 9 7 4 本章小结一1 0 1 结论。1 0 3 1 主要工作和贡献”1 0 3 2 未来工作一10 5 参考文献“10 7 攻读博士学位期间取得的研究成果11 3 致谢l1 4 v n v 1 1 1 第1 章绪论 i ii 第1 章绪论 为了克服自身信息和资源的有限性，网站、个人、服务器等实体通常通过 协作来完成各式各样的服务需求，从而增强市场竞争力。而随着信息和资源的 爆炸式增长，传统的集中式协作技术和方法已难以适应大规模的、开放的、动 态环境，如i n t e m e t 【、p 2 p 网络【2 】、g r i d 3 1 、计算云【4 1 、易趣网【5 1 、物流网络1 6 】 等。因此，分布式协作成了实体新的选择，其相关问题也引起了研究人员的关 注，如伙伴搜寻问题。信任关系作为实体间的一种重要社会关系，能帮助 用户在上述环境中挑选文件、信息、服务及其供应商【1 2 。6 1 。然而，上述环境的 复杂特性【限1 9 1 和信任固有的不确定性、动态性【2 0 , 2 1 1 限制了其在实际中的应用。 1 1 课题背景 现代信息技术及互联网技术的迅速发展为实体交互带来便利的同时，也加 剧了它们之间的竞争。实体在方便快捷地发布文件、传递资源、共享计算能力 的同时，需要面对更多的对手、应付更多样化的需求。在此趋势下，单个或少 数实体无法集中地组织和管理实体间有效信息，进而负责协调实体间的各种交 互。因此，分布式协作成了实体克服自身能力和资源的有限性、增强市场竞争 力的重要解决方案。而作为实现分布式协作的重要步骤，协作伙伴的搜寻在很 大程度上决定了协作结果的好坏。 有效地搜寻协作伙伴对实现云计算4 ，2 2 1 、分配任务【2 3 】、定位资源【9 ，1 1 2 4 】等 实际应用有十分重要的意义。譬如在云计算模式中，遍布在全世界的服务器按 用户的需求实时地存储数据或运行程序。它们在一秒钟内需要完成数以百计甚 至是千计的用户需求。而每个用户的需求又通常由多个服务器协作完成。因此， 当收到用户提交的需求后，如何快速找到能协作成功完成此需求的服务器是实 现和普及云计算的关键问题。 上述观察促使本文对大规模的、开放的、动态的分布式环境中的协作伙伴 搜寻这一问题展开了研究。复杂网络学科的兴起为描述此类环境及其中的实体、 关系提供了一种新的、系统的思路【1 3 1 9 ，2 5 1 。同时，研究人员已经意识到，信任 北京工业大学工学博士学位论文 关系能帮助实体从海量对象中挖掘出特定目标，如信息资源或供应商等【1 2 1 。下 面，我们将分别阐述复杂网络和信任关系这两个研究热点。 1 1 1 复杂网络 自从揭示了复杂网络的小世界特征f 2 6 】和无标度性质【2 7 】以来，复杂网络研究 进入了一个新纪元【1 8 ，2 8 ，”1 。复杂网络研究的前提是基于图论的思想，用节点表 示物理或虚拟实体，用边描述实体之间的物理连接或逻辑关系。i n t e m e t 、p 2 p 文件下载网络、计算g r i d 等都可以形式化为面向服务的复杂网络，简称为服务 网络。这里的服务，是一个广义上的概念，包括具体的文件、信息等资源，也 包括计算能力等。 服务网络和复杂网络的复杂性不仅体现在节点、边、网络这三者的复杂特 性上，还体现在这三方面要素之间复杂的相互影响和作用。目前，研究人员已 经在复杂网络拓扑性质与建模【3 0 , 3 1 】、动力学性质、网络涌现行为【2 7 ，3 2 ，3 3 1 、复杂 网络的鲁棒性与脆弱性控制等方面取得了长足的进展【1 7 3 4 1 。但是，复杂网络的 动态性及相关相关，譬如网络演化机制、实体行为对网络演化的影响等，都还 有待于进一步研究 1 7 , 3 5 】。简单地说，复杂网络的动态性表现为两方面：1 ) 节点 允许自由地离开网络或加入网络；2 ) 节点不间断的相互操作，导致边的不断变 化。节点和边的不断变化影响网络整体拓扑和特性；反过来，网络整体特性又 能影响节点操作和边的变化。 面向自治的计算( a u t o n o m y o r i e n t e dc o m p u t i n g ) ，自从2 0 0 1 年被提出以 来，根据自底向上的原则，在刻画复杂网络方面取得了一定的成果【3 6 。9 1 。利用 面向自治的计算刻画复杂网络的核心思想是：在刻画网络最小单元，即节点( 实 体) 已知的、简单的状态和行为以及它们之间耦合关系的基础上，观察并描述 复杂现象，如过冲现象【删等，并挖掘导致复杂现象涌现的潜在机制。可以说， 面向自治的计算这一范式体系，为研究复杂网络中的动态性及相关机制等问题 提供了一种新的思路和方法。 1 1 2 信任关系 信任关系是现实世界中实体间的一种基本耦合关系。在计算机学科内，信 一 一一 第l 章绪论 任关系的研究主要涉及如何评估信任关系【4 卜4 4 1 以及如何基于信任关系解决个性 化推荐、p 2 p 文件下载、g r i d 服务调度等服务相关问题【1 3 - 15 1 。现有研究已经初 步表明，信任关系能帮助实体提高服务效率或质量【1 3 1 5 ，4 5 1 。此外，目前研究人 员已经开始尝试用复杂网络方法研究信任关系，将实体间的信任关系映射成为 网络中的边，并用复杂网络的结构统计性质描述实体间的信任关系状态【4 6 1 。 然而，在现实的分布式协作环境中还很少引入信任关系。一方面，在现实 环境中，实体不断产生、消逝，而且实体间不断交互。另一方面，虽然人们已 经意识到信任关系随实体交互经验和时间变化而不断变化，但还不明确信任关 系与交互经验、时间之间的关联，更不用说具体的变化机制f 2 0 ，4 7 ，4 8 1 。 从上面对复杂网络和信任关系研究的简单介绍中，可以看出，基于复杂网 络学科的成果和方法研究分布式协作环境中的信任关系动态性具有可行性，也 富有挑战性。这些研究将拓展复杂网络动态性和演化机制的研究，同时促进信 任关系在现实环境中的应用，更好地解决分布式协作问题。在此背景下，本文 开展了相关研究工作。 1 2 本文主要研究内容 如上所述，本文将针对伙伴搜寻问题，研究分布式协作环境下的信任关系 动态性。在对相关研究进行收集、整理和分析的基础上，本文就以下具体问题 开展了相关工作： 1 2 1 信任关系对服务网络和实体的影响 e i g e n t r u s t 4 9 1 、f i r e 5 0 1 、s u n n y 5 l 】等模型的提出者为了证明模型的有效 性，在不同程度上讨论或验证了信任关系在解决不同实际问题时的好处。这些 工作都集中在对服务网络性能方面的讨论，忽略了对服务网络结构以及实体间 关联的讨论。然而，一方面，仅对服务性能改变的讨论，无法对信任