一種新的基于博弈論的Ｐ２Ｐ激勵機制
2008-12-31 00:00:00徐海湄鄭相全齊守青聶曉文
計算機應用研究 2008年9期
摘 要：針對P2P系統中的搭便車和公共悲劇問題，提出了一種基于博弈論的激勵機制。每個節點從個人理性出發，在最大化個人收益的同時根據請求者的貢獻分配帶寬，并利用動態規劃方法求出了最優解，實現了有限資源的帕累托配置，達到了社會收益最大化的目的。仿真實驗表明，該激勵機制促進了社會收益的快速增長，達到了激勵節點參與資源共享的目的。
關鍵詞：不完全信息靜態博弈; 帕累托; 社會收益; 個人收益; 動態規劃
中圖分類號：TP393 文獻標志碼：A
文章編號：10013695(2008)09278703
Novel incentive based on game theory in P2P networks
XU Haimei1，2， ZHENG Xiangquan2， QI Shouqing2， NIE Xiaowen1
(1.School of Computer Science Engineering， University of Electronic Science Technology of China， Chengdu 610054， China; 2.College of Chongqing Communication of PLA，Chongqing 400035， China)
Abstract:In order to solve free rider and tragedy of the commons problems in peertopeer(P2P) systems，this paper proposed a novel incentive based on game theory. Whiletrying to maximize its own utility subjected to individual rationality， every peer allocated bandwidth resources efficiently according to competing peers’ contribution values to maximize the social utility. The simulation result shows that the incentive increased the social utility of the whole P2P system rapidly and incentive every peer to share resources effectively.
Key words：static game with incomplete information; Pareto; social utility; individual utility; dynamic programming
傳統的P2P系統沒有提供有效的激勵機制，導致了搭便車和公共悲劇的發生。文獻[1]指出，在Gnutella中，70%的用戶從來不共享任何文件，50％的文件查詢響應來自1％的共享用戶。文獻[2]提出的Eigentrust和文獻[3]提出的Peertrust是比較經典的用來解決搭便車現象的聲譽模型，每個節點通過文件交易累積聲譽，聲譽值大的享受更好的QoS。但是聲譽的累積需要目擊者(witness)提供信息[4]，并且容易受到洗白(whitewash)和共謀(collusion)行為的攻擊[5]。文獻[6]首次提出將微支付的方法引入激勵機制，并用博弈論分析了可行性。微支付強調上傳文件收費，下載文件付費，因此不存在洗白和共謀現象。但是微支付要求第三方進行繁雜的審計工作，這與P2P理念相背，容易造成單點失效現象。還有大量文獻[7~9]致力于激勵機制的研究。
在P2P文件共享系統中，節點通過下載文件獲得收益，通過上傳文件作出貢獻。當多個節點向同一個節點申請下載文件時，貢獻越多的節點應該得到更多的資源分配。但是在節點的互動博弈[10]中，每個節點都從個人理性（individual rationality）出發，以最大化自身收益為目標選擇決策行為，而不考慮其他節點。能否通過機制設計(mechanismdesign)使個人收益最大化的同時實現社會收益（social utility）最大化呢？這就是激勵機制要達到的目的：a）公平性，貢獻越多，收益應該越多；b)資源的有效利用，資源的配置可否達到帕累托（Pareto）最優；c)個體理性與激勵兼容的實現，即個體收益最大化的同時實現系統收益最大化。
1 不完全信息靜態博弈模型的建立
在P2P系統中，每個節點都是對等的，既是客戶機又是服務器。以文件傳輸過程中不同節點通過競爭帶寬資源獲得收益，最后達到一個均衡為例建立博弈模型。
為了敘述方便，引入以下符號：
N為P2P系統的節點個數；
xi(t)為在t時刻，當節點i要求文件下載時，得到的實際下載帶寬；
di(t)為在t時刻，節點i要求的最大下載帶寬；
ui為節點i的最大上傳帶寬；
ci(t)為在t時刻，節點i的貢獻值；
為了討論方便，以xi代替xi(t)，di代替di(t)，以ci代替ci(t);
Rk為向節點k申請文件下載的節點集合，如圖1所示。
Rk=[1，2，3，4]，表示節點1、2、3、4向節點k要求分別以速度d1，
Θ=(θ1，θ2，…，θN)，Θ是所有參與競爭節點的類型，對于每個節點i，θi是要求下載帶寬di，上傳帶寬ui和貢獻值ci的函數，如θi=（4，2，5）表示節點最大要求下載帶寬為4 Mbps，上傳帶寬為2 Mbps，貢獻值為5，每個節點的貢獻值對于系統的所有節點是公開信息；
Ui=(di，xi)為節點i的收益函數，其中Ui 是節點i要求的最大下載帶寬di與分配帶寬xi的非負函數。
分析圖1，在t時刻，四個競爭節點1、2、3、4向節點k要求文件下載服務，節點k的上傳帶寬為uk，這些競爭節點分別發送決策信息d1、d2、d3、d4給節點k，告知需要多少下載流量，節點k從自身利益最大化出發，決策如何分配帶寬資源。節點之間可以動態調整決策信息，直到達到一個均衡。顯然節點間的互動博弈是一個不完全信息靜態博弈[11]，因為每個節點并不完全了解其他節點的類型信息，并且多個節點競爭同一帶寬資源時的決策與時間順序無關。
2 激勵機制
傳統的激勵機制類似文獻[2，3]，僅僅以節點的貢獻值作為激勵值，沒有考慮每個節點的收益。博弈論認為，用個體收益激勵節點更理性。
定義1 節點貢獻值。節點i的貢獻值等于所有請求節點通過從i處下載所獲得的收益之和減去節點i從其他節點處下載所獲得的收益，即
Ci(t)=∫t0∑Nj=1Uj(dj，xj)dt-∫t0Ui(di，xi)dt t＞0
SU=∑Ni=1Ci(t) t＞0(2)
定義3 節點的個體收益。在t時刻，節點j向節點k要求文件下載流量dj，一旦獲得下載流量xj，節點就會獲得收益，即
式（3）表示節點j的收益等于分配到的帶寬與最大要求下載帶寬的比值。收益類似于滿意度，要求的少，得到的多，滿意度就越高，收益就越大，就越愿意貢獻資源給系統，當xj=dj時，收益為1，滿意度最高。
2.1 個體收益最大化
博弈論中指出：個人理性使個體追求自身利益最大化，即當n個節點1…n向節點k申請下載文件時，k會通過分配傳輸帶寬使收益最大，即
F(x)=arg max (∑ni=1Ui(di，xi)） s.t. ∑ni=1xi≤uk(4)
定理1 式（4）的解是一個納什均衡解。
證明過程見文獻[11]中囚徒困境的納什均衡解。但是囚徒困境的納什均衡解揭示：從個體理性出發的決策行為不能實現團體的最大利益，最終也不能真正實現個體的最大利益。
2.2 社會收益最大化
式（4）僅僅考慮了個體收益最大，如果將每個節點的貢獻因子也考慮進去，合理分配帶寬資源，能否達到資源分配的Pareto最優，從而實現社會收益的最大化呢？
因為節點1…N對P2P系統的貢獻值各不相同，所得到的收益就應該有所區別，貢獻越多，收益應該越大，從而激勵活躍節點貢獻更多資源，懶惰節點變為活躍節點。因此加上貢獻因子ai，式（4）演變為
23 具有激勵機制的傳輸帶寬分配算法(TBDA)
式（5）主要考慮節點的收益和貢獻兩個競爭因素作為激勵因子。對于請求者來說，在請求帶寬不變的情況下，貢獻越多，其獲得的帶寬就越多；另外在貢獻相同的情況下，請求的帶寬越少，其獲得帶寬的可能性就越大。
對于式（5），可以用動態規劃方法求出最優解。
用動態規劃求解問題的最優解的基本思想是：首先求解部分問題的最優解，再求更大部分的最優解，直到最后求出整個問題的最優解。
設用Fm(x)表示節點k將上傳帶寬uk分配給1…n個請求節點中的前m個節點所能得到的最大總收益，則由最優原理可以導出如下遞歸方程：
由式(6)遞推地求出F1(uk)，F2(uk)，…，Fn(uk)以及x，Fn(uk)就是問題的最優解。例如，已知d=[1，2，5，2，5，4]，c=[2，5，1，2，5，4]，uk=7.0，由式（6）求得x=[1，1，2.5，2.5]，此時節點k的最大收益為0.79。
傳輸帶寬分配算法(transfer bandwidth distribution algorithm，TBDA) 的偽代碼如下：
(1)Sort ci*(1/∑ni=1ci)*(1/di) in descending orders. store values and node index in array a and t
(2)Fn(uk)=0; // initialize max utiliy=0
(3)Store the number of peers with the same value in array a to array t1
(4)i=1 ； //initialize index variable
(5)Vol=d[t[1]；
//peer with larger value in array a will get bandwidth in priority
(6)do{
(7)num=t1[i];
//the number of peers with the same value in array a
(8)if (vol*num>=u)
//the same peers will get the same bandwidth
(9){ for(k=0;k (10){x[t[i+k]]=u/num; (11)u=0;} //bandwidth used up (12)else{//move to next peer (13){for(k=0;k (14){ x[t[i+k]]=vol; (15) i=i+num; (16)u=u-vol*num; (17)vol=d[t[i]];} (18) } (19) while(u>0); (20) for (i=1;i<=n;i++) (21)Fn(uk)=Fn(uk)+(ci/∑ni=1 ci)* (1/di) //store the max utility in Fn(uk) (22) Return x; //peers’ bandwith stored in array x 定理2 利用動態規劃法求出的帶寬分配向量x=[x1，x2，…，xn]是Pareto最優的[11]。 證明 當所有節點要求的帶寬∑ni=1di≤uk時，xi=di，每個節點都得到最大收益1，當所有節點要求的帶寬∑ni=1di≥uk時，uk被充分利用，任何一個節點的收益增加都會損害另外節點的收益。因此在帶寬資源的分配存在著的pareto最優配置，這在博弈論中是一個人人歡喜的結局[11]。 3 實驗仿真 為了評估基于激勵機制的帶寬分配算法，進行了仿真實驗，在P2P仿真系統中，假設有1 500個節點，節點分為三類：30％為自私節點(selfish node)，該節點的貢獻值為0，30％的節點為無私節點(altruistic node)，該類節點貢獻值大于0，40% 為混合節點(mixed node)，該類節點有時候自私，有時候無私。 首先，對比了基于激勵機制的P2P系統和沒有引入激勵機制的情況下，利用式（2）計算出的P2P系統總收益隨時間的變化。結果如圖2所示。從圖2中可以看出，引入了激勵機制的P2P系統，系統總收益隨著時間逐漸遞增，而沒有激勵機制的P2P系統，在前20 min內，系統總收益逐漸遞增，之后直線下降，這是因為隨著搭便車行為的增多，無私節點和混合節點逐漸加入了自私節點的陣營。 其次對比了基于激勵機制的P2P系統和沒有引入激勵機制的P2P系統的情況下，各類節點服務質量的情況。服務質量用成功下載率SDR(successful download ratio) 衡量。SDR=下載成功次數/要求下載的總次數，結果如圖3所示。 從圖3中可以看出，在一開始時，文件交換還不頻繁，各類節點下載成功率比較高，隨著文件交換越來越頻繁，貢獻值小的節點獲得的帶寬越來越小，最后減至0；而無私節點的貢獻值大，QoS得到了保證，成功下載率就維持在一個比較高的水平；混合節點為了得到較好的服務，逐漸終止自私行為，向無私節點轉換。 4 結束語 本文提出的基于博弈論的激勵機制，不同于以往的聲譽機制與微支付機制，將個人收益和貢獻值綜合考慮作為激勵因子，在帶寬資源的分配方面實現了Pareto最優，社會收益因此提高。仿真結果證實，激勵機制實現了抑制自私節點，鼓勵無私節點與混合節點多做貢獻資源的目的。 參考文獻： [1]ADAR E，HUBERMAN B. Free riding on Gnutella[EB/OL].(2000).http://www.comp.nus.edu.sg/~bleong/p2pft/related/adar00free.pdf. [2]KAMVAR S D， SCHLOSSER M T. EigenRep: reputation management in P2P networks[C]//Proc ofthe 12th International World Wide Web Conference. Budapest， Hungary: ACM Press，2003:123134. [3]XIONG Li， LIU Ling. PeerTrust: supporting reputationbased trust for peertopeer electronic communities[J].IEEE Trans on Knowledge and Data Engineering，2004，16(7):843857. [4]SABATER J， SIERRA C. Review on computational trust and reputation models[M].Norwell:Kluwer Academic Publishers，2005:3360. [5]FELDMAN M，CHUANG J. Overcoming freeriding behavior in peertopeer systems[J].ACM SIGecom Exchanges，2005，5(4):4150. [6]CONE P，LEYTONBROWN K，MIMNOV I.Incentive for sharing in peertopeer networks[C]//Proc of ACM Conference on Electronic Commerce.New York:ACM，2001:264267. [7]COURCOUBETIS C， WEBER R. Incentives for large peertopeer systems[J].IEEE Journal on Selected Areas in Communications，2006，24(5):10341050. [8]SANGHAVI S， HAJEK B. A new mechanism for the freerider problem[C]//SIGCOMM’05 Workshops. Philadelphia:[s.n.]，2005:122127. [9]MA R T B， LEE S C M， JOHN C S，et al. An incentive mechanism for P2P networks[C]//Proc of the 24th International Conference on Distributedcomputing Stem.[S.l.]: IEEE，2004:516523. [10]HARSANYI J. Games with incomplete information played by Bayesian players[J].Management Science，1968，14(5):320334. [11]SHI Xiquan. Game theory[M]. Shanghai:Shanghai University of Finance Economics Press，2000.
