2011年8月计算机工程第37卷第15期August 2011 Computer Engineering 文章编号100←3428(2011)15→0协-ø3文献标识码A中回分类号·网络与通信·基于博弈论的P2P激励机制张娓娓陈蟹阳13，余洋3(1.西安思源学院电子信息工程学院，西安710038;2西安交通大学信息科学系，西安710049;3.华北电力大学电气与电子工程学院，河北保定071003)摘要:对等(P2P)网络中的搭便车问题使得网络节点只享用信息资源服务而不为系统贡献资源，导致网络中的共享资源不断减少，严重影响P2P网络系统的性能。为此，根据搏弈论中的纳什均衡理论提出基于RDEC算法的激励机制。通过模拟实验并对相关数据进行分析，结果表明，该策略能改进P2P网络中资源的公平共享，最大化系统的效用。关键词:对等网络;博弈论;激励机制;纳什均衡理论;资源分配P2P Incentive Mechanism ased on Game Theory 13 ZHANG Wei-wei\ CHEN Sui_yang,2, YU Yang(1. School ofElectronic Infonnation Engineering, Xi’an Siyuan University, Xi’an 710038, China; 巳'partrnentof Information Scienc巳，Xi'anJiaotong University, Xi’an 710049, China; 3. School of Electrical and Electronic Engine唱ring，North China Electric Power University, Baoding 071003, China) (Abstract)The free-riding problem in Peer-to-Peer(凹的networkmakes nodes only use infonnation resources instead of contributing resources for 出esystem. It leads resources continue to decrease, which seriously affects the P2P network system p巳 solve th巳problem，this paper proposes a P2P incentive mechanism based on RDEC a1gorithm by using the Nash equilibrium theory. Simulation experiments and th巳analysisof its data demonstrate出estrategy can improve resource sharing fairly and maximize the system utility. (Key words) Peer-to-Peer仅2P)network; game theory; incentive mechanism; Nash equilibrium theory; resource distribution DOI: 复杂的审计工作，容易造成单点失效现象。还有很多研究者1 概述都致力于激励机制的研究[5-6]。但是这些激励模型都是基于节随着科学技术的发展，对等(Peer-to-Pee，P2P)网络逐步深点贡献值的，忽略了节点的自身收益。仅依靠节点的贡献值入到人们的学习、工作和生活中。P2P技术不同于传统网络来激励节点是一种强迫行为，其结果可能会使大部分节点贡技术，它的本质思想是:打破传统的客户/服务器模式，让一献资摞。但是节点在贡献资掘的同时也在追求其自身的收益，切网络成员享有自由、平等、互联的功能，使任意2个网络只有同时通过增加节点的收益，节点才可能去主动调整策略，节点之间都能共享文件、传递消息。P2P网络中节点自由通贡献更多的资源。信、平等交流和互联的特点，使得P2P网络技术得到了迅猛因此，本文综合考虑了节点的贡献值和收益值2个方面，的发展。但同时这些特性也使得P2P网络存在"搭便车"(free›在博弈的基础上提出了RDEC算法，由此来激励节点积极参riding)问题。与贡献、分享资源。所谓free-riding问题，是指P2P网络中的节点只享用信息资源服务而不为系统贡献资掠所带来的共性问题[1-2]。这一2 基于博弈论的P2P激励模型的算法分析和实现现象的出现，导致网络中可共享的资源不断地减少，严重影对P2P网络中的激励机制进行研究主要是为了解决free响到P2P网络系统的性能。文献[1]描述了Gnutel1a系统中节riding问题。如果缺乏合适激励机制的P2P文件分发系统会点24h的运行活动。在这24h中，系统中大约有70%的节导致F载速度变慢和下载时间变长，而在P2P流媒体中，会点不去共享其本身的资源，47%的下载任务都交给了1%的节造成播放不连续、黑屏或者马赛克的问题。本文的目标就是点来完成，另外25%的节点承担了系统中99%的下载任务。找到一种合理的并且能够针对不同系统特点的激励机制，来这一问题的存在，大大降低了P2P网络的公平性，同时也降促进节点的合作，从而达到优化网络性能的目的。激励节点低了网络的整体性能，结果严重影响了用户的利益。显然，在贡献自己资源的同时，尽可能使每个参与节点的媒体质量free-riding现象与P2P通信模式提倡的协作共享理念是不一都能满足QoS的需要。致的。free-riding行为的蔓延将导致P2P系统中的节点无法 基于撒励值的橄励机制公平共享系统资源，如果不对这种现象进行遏制，那么 节点贡献植的确定系统有可能会退化为传统的客户端/服务器模式。许多P2P系P2P网络中的节点在向系统提供服务的同时，也在享用统依赖于兴趣节点之间的合作，但因为合作会消耗节点的资源并可能带来性能的降低，所以每个节点都试图最大化自己基金项目:华北电力大学青年教师科研基金资助项目(200911001)的效用，结果导致系统的总体效用降低[3]。作者筒介:张娓娓(1978一九女，硕士研究生，主研方向:P2P技术;文献[4]最早提出将微支付的方法应用到激励机制上，并陈绥阳，教授;余洋，硕士用博弈论分析了可行性。但是微支付的方法要求第三方进行收稿日期2011-03-21 E-mail: weiweizhang_nwu@
90 计算机工程2011年8月5日系统中其他节点为他提供的服务。节点之间的交互是双方的、在图1中，2个最优函数只有一个交点，这个交点就是互利的，故在确定节点贡献值的时候，不能仅以节点提供的最优组合一←纳什均衡问，乓)，这时效用函数取得最大值。服务来确定，而是要同时计算节点被提供服务的开销。上文对于2个节点的纳什均衡证明，对于多个节点的P2P设节点的贡献值为C(i)(Contribution)。设up(i)为节点上网络也是适用的。传的资源，即共享的资源。down(i)为节点享用的资源，也就假设节点选择是通过gossip方式进行的，节点i在所有是下载的资源。由此可以得到节点的贡献值:邻居节点范围内发布广播消息，查询节点贡献值以及其他节C(i) = up(i) -down( ) 0 < < N (1) 点对它的贡献值，亦即节点的贡献值和收益值。本文的目标是激励节点贡献更多的资源，使得整个系统在结合纳什均衡理论中的伯川德双寡头垄断竞争模型的效益最大化:后，P2P网络中的节点为了从其他邻居节点获得较好质量的maxC(i) O<i<N (2) 服务，就必须尽可能地增加自己的贡献，使系统达到一个新 节点效用函数的确定的均衡，从而在一定程度上避兔了节点的free-riding现象，因为节点在博弈的过程中，除了提供服务外，还要求自增加系统的总效用。身收益也达到最优，这个自身收益就是其他节点对它的贡献 基于激励值的资源分配方法分析值，所以对于节点的效用函数，需要综合考虑节点的贡献值通过上面对节点贡献值和节点效用函数的讨论分析，可和自身的收益值。把节点的收益值定义为E(i)(Earning): 以得知节点为了达到纳什均衡，在进行策略选择的时候追求(3) E(i)=p; L e; 自我的收益达到最优，节点的策略空间与节点的贡献值、节。<j<N，j冉v点的效用值息息相关。因此，在这里设定节点一个交易周期其中，e表示所有其他节点J对节点i的贡献值E(i)表示J的激励值为:节点i可以从系统中其他节点得到的收益，也就是其他所有l(i) =αC(i)+βE(i) (8) 节点对节点t的贡献值之和。故节点的效用函数可写为:其中，α+β=1;α为贡献因子;β为收益因子;α，βε[0，1]。U(i)=E(i)-C(i)=p; L e;-C(i) O<i<N (4) 。<j<N，ii: RDEC算撞撞程和解决方案在本文所设计的激励机制中，p;表示其他节点为节点i根据上文的研究结果，设计一种基于收益值和贡献值的资源分配算法(ResourceDistribution algorithm based on 提供资源共享的概率，Pi的获益取决于其他节点对系统的贡Earning and Contribution, RDEC)。献值，它与节点i的贡献值C(i)成正比。Pi越小，说明节点i算法的框架结构如图2所示。的请求越有可能被拒绝，Pi是一个单调递增的函数:L C(j) Pi=~勾""n(5) 一ι1+ L C(j) 。ε主j运n上面讨论的节点1和节点2，只有两者选择的策略达到了纳什均衡，才能够获得较大的利益。根据纳什均衡理论，只有效用函数满足单调性和凹性，最合理的资源共享方案就一定存在。不仅每个参与节点都能够获得最大效用，同时系统也可以获得最大的总效用，个体优化和整体优化的统一意按照效用激励值I(i)分配资源味着个体间的公平和整体效率的提高。设节点1、节点2能获得的最大利益分别为可和P;，则回2资部分配憾弈模型根据前面的伯川德双寡头垄断竞争模型，对于节点1来说，算法的设计步骤如下:如果节点2选定的最大利益为可，则可以得到节点l的最大(1)申请资源的节点都以自己的最大效用函数值来进行利益的方案为:申请。C(I) (2)通过RDEC算法，按照效用函数值的高低，优先分配巧=一一，::"'.E; -C(I) (6) 1+C(I) " 资源给效用函数值高的节点，而效用函数低的节点延迟分配其中，E;'(í=1，2)表示节点所获得最大收益。同理，可以得到或者无法分配到资源。节点2的最大利益的方案为:(3)算法分为2个部分。一部分是从请求节点来计算节点C(2) 的贡献值，也就是节点对其他节点的历史资源分配情况;另P2 =一一一-:-:E; -C(2) (7) I+C(2) . 一部分是从请求节点的邻居节点来考虑节点的效用值，亦即根据可、Ff的单调性，可以得到最优组合(矿，可)，见其他节点对请求节点的贡献值。图1，可、P'的函数曲线的交点(芹，可)即所求的最优组合。RDEC算法由请求端系统和服务提供端2个部分组成，2E 首先讨论请求端系统上的实现部分rdecclaim，下面给出了上述算法的伪代码描述:算法请求端系统RDEC算法的执行输λ请求节点的效用值E(i)和贡献值C(i)输出请求节点的策略空间rdecclaimO o P,’ C, fetch(E(i),C(i)); //获取节点的效用值和贡献值回1最优组合函数曲线
第37卷第15期张娓娓，陈绥阳，余洋:基于博弈论的P2P激励机制91 accountU(U(i)); 1/根据式(4)计算效用函数的激励机制系统中则相反，自私类节点所占的百分比下降很accountP(P叩));//根据式(6)计算能获得的最大益快，最终稳定在10%左右。相比较于RDEC算法的激励机制accountI(i); //根据式(8)计算节点的激励值来说，Tit-for-tat的自私类节点数量始终要比本文所提激励机submitS(U(i), P*(i),I(i)); 1/向资源提供者提交策略制的自私类节点要多。由此可以看出，该激励机制能有效抑制节点的自私行为，为系统的良性发展奠定基础。下文再给出资摞提供端上的实现部分rdecprovide，伪代100 码如下:90 算措资源提供端系统RDEC算法的执行80 J Z告70输入请求节点的数量N和各个请求节点的策略空间罢60输出最优策略空间，并分配资源主50rdecprovideO 草40ili1 3。但coIlect(U(i)，俨(i));//收集请求端系统的各个策略空间sort(U(i),P*(i),I(i)); //根据收集到的策略空间，对请求端10 H的节点进行排序20 40 60 80 100 120 140 160 180 200210 broadcastS*(U(i), P*(i)); /1广播当前请的最优策略时间18for l<i<N 回4系统中自私节点随时阔的变化if S(U(i), P*(i))>= s*(U(i, P*(i)) 实验2系统总效用，即所有参与节点的效用总和then distribute resources; //向最优策略分配带宽图5显示了系统效用的变化。当节点不采取激励机制时，RDEC模型的流程如图3所示。系统效用显示了一个随机分布，且系统效用不高。而在有激励机制时，系统的效用随着时间的增长在不断增长。可以看出，计入激励机制的系统性能明显要好于没有撒励机制的系统。Tit-for-tat激励机制和RDEC算法的激励机制相比，后者的系统总效用耍高于前者，并且总是处于稳定的状态。再次证明了该机制的有效性。 匮祺玛螺0U9。AU8 5Mm----~ ------~ -卢-----/ I--~ ~ ~ -~ I_I~I~I_I~ 时间1，回5不同模式下的系统总效用实验3系统负载系统负载是考察系统总体性能的→个重要参数，用请求资源的节点总数与提供资源的节点总数之比来计算系统的负载。当用户节点增多时，网络中用户节点之间共享数据的概率也增大了，因此，系统负载随着节点数量的增加而降低，结果如图6所示。100 90 回3RDEC模型11程80 No Incentive ::;-70 3 实验结果与分析F RDEC 这60Tit-for=tat 采用NS2作为仿真器，GT-ITM创建网络拓扑。为了评~ 50 \ 价RDEC算法的性能，也仿真了没有加入激励机制(No~ 40 \ 、叫30町-h -『~『Incentive)的方案和Tit-for-tat模型，并将3种算法的性能加\』、-20 h、z 一-›10 以比较。为了检查系统的有效性和效率，采用了以下参数:(1)随着时间的变化，系统中自私类节点的变化情况(2)系统o 200 400 600 800 1 000 1 200 1 400 节点个数总效用，即所有参与节点的效用总和(3)系统负载，用请求回6系统负就变化资源的节点总数与提供资源的节点总数之比来计算。 仿真结果与分析从图6中可以看出，随着节点数量的增多，RDEC算法实验1系统中自私类节点的变化的系统负载总体上比Tit-for-tat算法的系统负载要小，而没有从图4中可以看出，在没有激励机制的P2P系统中，自加入激励机制的系统负载明显要高。因此，在→定的程度上私类节点随着时间的变化很快地上升。而在加入RDEC算法RDEC算法的系统负载相对最小。(下转第102页)
102 计算机工程2011年8月5日较结果，其中，Pair表示双线性对运算Mul表示椭圆曲线的安全级别所需密钥量要小的多，比如密钥量为160bit的椭标量乘运算Exp表示指数运算x(+y)表示x次双向性对运圆曲线数字签名算法(ECDSA)就能达到密钥量为1024 bit的算和y次双线性对预运算。显然，在不考虑双线性对预运算数字签名算法(DSA)的安全级别IBI;(均不需要对公钥进行认的情况下，本文算法在计算量方面优于文献[7]算法。证、维护。因为该算法是基于身份的，其公钥是根据用户身份信息产生的，是惟一的、确定的，所以不需要对公钥的证表1签密模式下的计算量比较书进行认证，也无需大存储容量的节点来存储众多用户的公签密解签密算法钥证书;(3)以少量的密码组件，实现多项密码功能。广义签Mul Pair Exp Mul Pair Exp 密算法以一个密码模块完成签密、加密和签名三项密码功能。文献171算法o 2 。参考文献本文算法。(+1)0 3(+1) [1] Zheng Yuliang. Digital Signcryption or How to Achieve Cost(Signa›ture and Encryption)<<Cost(Signature) +Cost(Encryption) [C]/lProc. 表2加密模式下的计算量比较ofCRYPTO’97. [.]: Springer-Verlag, 1997. 加密解密算法[2] Shamir A. Identity-based Cryptosystems and Signature Sche›Mul Pair Exp Mul Pair Exp mes[C]/lProc. ofCRYPTO’84. [.]: Springer-Verlag, 1984. nυ nu 文献17J算法。[3] Boneh D, Franklin M. Identity-based Encryption from the Weil Pairing[C]//Proc. of CRYPTO’OI. [S. 1.]: Springer-Verlag, 2001 本文算法。(+1)0 。[4] Malone L J. Improved Identity-based Signcryption[M]. Berlin, 表3签名模式下的计算量比较Germany: [s. n.], 2005. 签名验证[5]李腕，何明星，罗大文基于身份的签密方案[J]计算机工算法程，2009，35(22):144-146 Mul Pair Exp Mul Pair Exp [6] Han Yiliang, Yang Xiaoyuan. ECGSC: El\iptic Curve Based 文献[7J算法4 。。Generalized Signcryption Scheme[EB/OL]. (2006-12-06). http:// 本文算法。。。2(+1) cat onl4534720/. [7] Sunder L, Prashant K. lD-based Generalized S gncryption[EB/OL]. 7 结束语(2008-08-04). http://epr 本文提出的基于身份广义签密算法与传统公钥算法相比[8] National Institude of Standards and Technology. FIPS PUB 186-2 具备以下3个优点:(1)密钥量相对较小。基于身份的广义签密Digital Signature Standard[S]. 2000. 算法是以椭圆曲线为基础的，与传统公钥算法相比，达到相同编辑陈文……---------------.....…----------叫…......--_..........-.....…---…--…………………--…………………------------------(上接第91页) 实验总结参考文献从仿真结果和分析来看，RDEC算法明显优于没有激励[1] Adar E, Huberman B A. Free Riding on Gnutella[R]. Palo Alto, 机制的P2P系统，同时也比Tit-for-tat的激励机制要好。从USA: Internet Ecologies Area X巳roxPalo Alto R巳searchCenter, 对RDEC算法所涉及的参数情况进行分析得到，该算法比较Tech. Rep.: SSL-00-63, 2002. 适合大部分节点是自私节点的P2P系统。也即是说，当系统[2] 余一娇，金海.对等网中的搭便车行为分析与抑制机制综中的大部分节点仅在清楚地看到自己利益的情况F才贡献更述[J]计算机学报，2008，31(1):1-15 多的资源，在这种前提下，当用户节点请求其邻居节点提供[3] 漏春林，朱同林，刘寿强，等.基于理性博弈的P2P网络激励模服务时，每次选择当前激励值较高的节点进行服务，这就使型[J].计算机王程，2010，36(14):79-81 得优先为激励值高的节点提供资源，这样有利于激励节点贡[4] Cone P, Leyton-brown K, Mimnov 1. Inc巳ntivefor Sharing in Peer›献自己的资源，减少free-rid巳r节点，提高系统的总体性能。to-Peer Networks[C]//Proc. of ACM Conference on Electronic 4 结束语Commerc巳.New York, USA: ACM Press, 2001: 264-267 本文对P2P网络中的free-riding问题进行了探索和研究，[5] Jun S, Mustaque A. Incentives in Bit Torrent Induce Free Rid 提出了基于博弈论的RDEC算法。实验结果表明，所提算法ing[C]/lProc. of SIGCOMM’05. Philaddelphia, USA: [s. n.], 2005 有效地激励节点贡献资源，提高了系统的总体性能。[6] Sun Qi, H巳ctorG M. SLIC: A Selfish Link-based Incentive 当然，对于fr∞-riding问题的研究还具有广泛的空间，Mechan sm for Unstructured Peer-to-Peer Networks[C]/lProc. of 笔者将在该方向继续做深入研究，如对于模拟实验中采用的the 24th IEEE Int’ 1 Conf. on Distributed Computing System. RDEC算法做进一步的探讨，研究服务评价机制以及如何克New York, USA: IEEE Press, 2004: 506-515. 服由于局部可靠性评估所带来的认识上的片面性，使其在整编辑任吉慧个网络中具有一定的客观性。
