（信号与信息处理专业论文）基于博弈论的p2p网络激励机制的研究.pdf

南京邮电大学硕：卜研究生论文摘要 基于博弈论的p 2 p 网络激励机制的研究 摘要 近年来，随着i n t e r n e t 技术的发展，p e e r - t o p e e r ( p 2 p ) 网络越来越成为人们关注 的焦点，然而p 2 p 网络是一种自组织、没有集中管理机制和基础设施的分布式系统，因为 其参与者的自发性和自治性，使p 2 p 网络中资源的可用性有着极高的变数和不可预知性。 并且在实际应用中，大多数参与者由于缺乏激励机制而不向其他用户共享自身资源，导致 传统的p 2 p 系统广泛地出现“免费搭车( f r e e - r i d i n g ) 问题，严重阻碍了p 2 p 技术和应 用的发展，由此引发了许多关于p 2 p 激励机制方面的研究。本文在使用博弈均衡理论的基 础上，提出一种基于博弈论的激励机制方法，可以用来提高p 2 p 系统性能和效率。 本课题研究的主要内容包括以下几个方面： 一、研究p 2 p 网络底层架构，以g n u t e l l a 为原型，引入p 2 p 网络专用设备( p e e rs e r v e r ) ， 以便为激励模型提供良好的底层网络平台。 二、构建p 2 p 网络文件共享系统的激励机制。这一部分首先分析了p 2 p 网络中参与者之问对 网络资源的竞争关系，并在非合作博弈n a s h 均衡理论框架下构造一个基于服务质量差异的 p 2 p 网络激励机制，分析不同性质的用户在相同激励机制下采取不同策略时的均衡状态， 得出最终的理想均衡状态，最后的仿真计算与分析表明可以消除f r e e r i d i n g 现象。 三、针对基于服务质量差异的p 2 p 激励机制存在的诸如效用函数随时间的变化不明显、激 励机制没有考虑节点收益情况等问题，提出前后时隙分析法。实验结果表明这种方法可以 有效的消除f r e e - r i d i n g 现象并提高系统的o o s 。 关键词：对等网描述符博弈论纳什均衡服务质量 t h er e s e a r c ho ni n c 日盯i v em e c 埘is mb a s e do ng a m e t h e o r yi np 2 pn e t w o r k s a b s t i 认c t w i t ht h er a p i dp r o g r e s so fi n t e r n e tt e c h n o l o g i e s ，p e e r t o p e e r ( p 2 p ) c o m p u t i n g i sc u r r e n t l yr e c e i v i n gc o n s i d e r a b l ei n t e r e s t h o w e v e r ，p 2 pn e t w o r k s a r e s e l f - o r g a n i z e d ，d i s t r i b u t e ds y s t e m s ， w i t hn oc e n t r a l i z e d a u t h o r i t y o r i n f r a s t r u c t u r e b e c a u s eo ft h ev o l u n t a r yp a r t i c i p a t i o n ，t h ea v a i l a b i l i t yo f r e s o u r c e si nap 2 ps y s t e mc a nb eh i g h l yv a r i a b l ea n du n p r e d i c t a b l e t h es e l f is h b e h a v i o ro fp e e r sm a yl e a dt os e r i o u sp r o b l e m so fp 2 pn e t w o r k ，s u c ha sf r e e r i d i n g a n dt r a g e d yo fc o m m o n s i no r d e rt os o l v et h e s ep r o b l e m s ，t h e r ea r ei n c r e a s i n g l y c o n s i d e r a t i o n so ni n c e n t i v ed e s i g ni nt h es t u d yo fp 2 ps y s t e m s i nt h i sp a p e r ， w eu s ei d e a sf r o mg a m et h e o r yt os t u d yt h ei n t e r a c t i o no fs t r a t e g i ca n dr a t i o n a l p e e r s t h ep r i m a r yc o v e r a g eo ft h i sr e s e a r c hp r o j e c th a ss u c ha s p e c t s b e l o w ： 1 b ya n a l y z i n gt h es t r u c t u r e so fp 2 pn e t w o r k g n u t e l l a ，an e wr o u t i n gp o l i c yi s p r o p o s e d ，w h i c hc a ne f f e c t i v e l yi m p r o v ei t ss c a l a b i li t ya n dr e d u c ei t sr e d u n d a n c y i nt h et r a n s m i s s i o no fi n f o r m a t i o n 2 b a s e do nt h i sn e t w o r km o d e l ，t h ei n c e n t i v ei s s u e st h a t a r i s ei ns u c h f i l e s h a r i n gs y s t e m sw illb ea d d r e s s e d f i r s t ，w ea n a l y z e dt h ec o m p e t i t i v er e l a t i o n s o fn e t w o r kr e s o u r c e sb e t w e e nt h ep a r t i c i p a n t si np 2 pn e t w o r k s e c o n d ，w e c o n s t r u c t e daf o r m a lg a m et h e o r e t i cm e c h a n i s mo ft h es y s t e ma n da n a l y z e d e q u i l i b r i u mo fu s e rs t r a t e g i e su n d e rs e v e r a ls i t u a t i o n s 3 b e c a u s et h ed i f f e r e n t i a ls e r v i c e b a s e di n c e n t i v e s c h e m ee x i s ts e v e r a l d i s a d v a n t a g e s ，s u c ha st h et r a n s f o r m a t i o no fr e p u t a t i o ni n d e xi sn o to b v i o u sw h e n t i m ev a r i a t e s w ep r o p o s e dt h ea n a l y t i c a lm e t h o db a s e do nt i m es l o ta n dc o m p e n s a b l e e a r n i n g s t h i sm e t h o dc a ne l i m i n a t et h ef r e e r i d i n gp r o b l e ma n di n c r e a s et h eq o s o ft h es y s t e m k e y w o r d s ：p 2 pn e t w o r k s ：d e s c r i p t o r ；g a m et h e o r y ；n a s he q u i l i b r i u m ；q o s n 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生张爽盈吼翌! z ：乡舌 南京邮电大学学位论文使用授权声明 南京邮电大学 - ( 一个完全的，可传递的，自反 的和二元的关系) 有时专门给定一个效用函数u ：c r 来表示决策主体偏好。效用函数 确定了一个偏好关系 - ，x - y 当且仅当u ( x ) u ( y ) 。 - 满足下列条件：给定一个集合b 量a ， a 为某个特别情况下的可能行动集合。一个理性决策主体选择一个可能行动口。似b ) 。若 口对所有口b i 茜足g ( a 。) - g ( a ) ，则口为最优的。为了对不确定情况下的决策建模，几乎 1 4 南京邮电人学硕士研究生论文第二章p 2 p 网络、博弈论及其激励机制 所有的博弈论都使用了v o nn e u m a n n 和m e r g e n s t e r n ( 1 9 9 4 ) 以及s a v a g e ( 1 9 7 2 ) 的理论。 也就是，如果结果函数是随机的并被决策主体已知( 即，对每一个口彳，结果g ( a ) 是集 合c 上的一个不确定事件) ，那么决策主体就被认为是为了最大化一个函数期望值( v - n - w 效用) 去行动，这个函数给每个结果赋一个值。如果行动与结果间的随机联系未给定，那 么决策主体就被认为是好像按照他心中的一个( 主观的) 概率分布去行动，这个分布决定 了任何行动的结果。在这种情形下决策主体被认为将这样行动，即他心中有一个“状态空 间”q ，一个q 上的概率测度，一个函数g ：彳xq _ r ；他被假定为考虑到概率测度去选 择一个行动口来最大化期望值u ( g ( a ，w ) ) 。 2 博弈论的策略 1 ) 纯策略( p u r es t r a t e g y ) ：指以绝对的态度在众策略中进行取舍，选取某一策略则一定 不取其他策略。 2 ) 混合策略( m i xs t r a t e g y ) ：跟“纯策略 相反，是指以相对的态度在众策略中进行取舍， 选取任一策略都是以一定概率进行的，但总概率必须等于1 。参与者的混合策略是他的纯 策略空间上的一种概率分布，表示参与者实际对策时根据这种概率分布在纯策略中随机选 择加以实施。 3 ) 最大最小策略：冯诺依曼和摩根斯坦认为策略的选择与决策者的性格有关。某些决策 者可能认为，冒失行动容易造成重大失误，最好还是从最不利的情况出发，向最好的方向 努力，力求做到有备无患。这样的决策者属于风险厌恶型的，他首先想到的是各种不利因 素和风险，所以他先要考虑各种最坏的结果，然后从最坏结果中选出一个最好结果。按这 种原则选取的策略可以称为最大最小策略。 4 ) 任何一个博弈，也许不存在纯策略纳什均衡，但一定存在混合策略纳什均衡。对于零 和博弈，若存在“最大最小策略均衡”，则该均衡必定是纳什均衡。混合策略中一定能找 到纳什均衡这一性质，使得混合策略更有实用性。同时，混合策略也更符合客观实际，一 则因为博弈的参与者选择策略时本来就不是确定无疑的，而是具有一定的随机性：并且， 每个参与者对于对手的策略选择的猜测也不是十分可靠的，这种猜测的命中率也是随机 的。二则因为混合策略对付反复进行多次的博弈为纯策略更很有效，而这种重复性博弈在 现实中更为普遍。在对博弈局势进行描述后，博弈论分析就是要求出参与者进行策略选择 的理性结局，或者说找出博弈问题的解。在非合作博弈中，有两种解的技术：一种是纳什 均衡，一种是优超解。 南京邮电大学硕士研究生论文第二章p 2 p 网络、博弈论及3 e 激励机制 2 5 5 纳什均衡( n a s h ) 1 ) 纳什均衡：对于博弈中的每一个参与者，真正成功的措施应该是针对其他参与者所采 取的每次行动，相