基于進化博弈的Ｐ２Ｐ網絡中信任計算的動力學分析

摘 要：運用動力學原理，基于進化博弈理論，對信任計算的動力學方程進行了求解分析，并運用復制動態原理分析了節點之間信任關系的演化趨勢，進一步揭示了信任計算的演化動力學規律。仿真實驗表明，進化是網絡節點信任合作的動力源泉。

關鍵詞：點對點網絡;信任計算;進化博弈;復制動態

中圖分類號：TP393 文獻標志碼：A 文章編號：1001-3695(2008)08-2460-03

Dynamics analysis of evolutionary game-based trust computing for P2P networks

LIU Feng-minga， DING Yong-shenga，b

（a.College of Information Sciences Technology， b.Engineering Research Center of Digitized Textile Fashion Technology， Ministry of Education， Donghua University， Shanghai 201620， China)

Abstract:This paper analyzed the dynamics of trust computing based on the evolutionary game theory in detail， and applied the replicator dynamics mechanism to analyze the evolutionary trend of trust relationships among nodes. The simulation results show that the trust and cooperative dynamics foundation is network evoluationary.

Key words: P2P networks； trust computing；evolutionary game； replicator dynamics

信任作為P2P網絡安全中的一個重要概念，是網絡節點之間關系的集合^[1]。但在P2P網絡中，沒有中心服務器和可信第三方提供擔保，這種關系的建立相當困難。因為用來評價信任的信息或證據有著非完整性、不確定性等特點。又因為P2P網絡的開放性、匿名性、自治性等，網絡中存在相當數量的惡意節點和自私節點，如傳播Sybil^[2]、Bad Mouthing、On-off^[3]等攻擊的節點以及大量的Free-Riders^[4]節點。這些節點的存在嚴重影響了整體網絡的性能，破壞了網絡系統的安全性和穩定性。因此，建立適當的安全信任機制，促進節點間信任合作，激勵誠信、懲罰失信是很有必要的。

目前，有關P2P網絡信任機制的研究，如EigneTrust^[5]、EigenRep^[6]、PeerTrust^[7]等，是通過收集節點的聲譽信息（即歷史行為）來計算節點的全局信任度。這種理想的模式要實現是很困難的，一是需要全局節點的配合，這也涉及信任問題；二是計算量和網絡通信開銷大。基于局部信息計算的信任模型，如Chord^[8]、P-Grid^[9]等，對于自治節點的來去自由又顯得“證據不足”。信任是社會生活的基本事實，是一種預期，是相信他人未來可能行動的賭博^[10]。因此，信任具有天生的不確定性和不可控性，這使得上述計算模型顯得有些“簡單”。

信任是網絡中一個節點對另一個節點的未來行為的預期，是一種博弈計算。對于經典博弈論的“完全理性”假設的現實性不足問題，Alchian原創性地提出了基于生物學進化論——“自然選擇”思想的制度演化模型^[11]，即進化博弈。而“復制動態”（replicator dynamics）機制在此模型基礎上假設博弈方為有限理性的，通過模仿、試錯等手段，改變其行為策略，并通過反復博弈和進化穩定策略實現動態策略調整及其演化穩定性。信任是一種簡化社會復雜性的機制越來越受到關注，因而，它作為P2P網絡安全的重要手段成為計算機網絡安全研究中的熱點。節點雙方信任關系的建立是通過節點不斷地考察、權衡，有著復雜的計算過程。因此，信任可以說是一個信任關系建立的計算過程，即策略決策過程；信任也是信任計算的結果，是一種策略。

基于進化博弈的思想，借鑒社會學、生態學的演化機理，對于信任計算的動力基礎進行了探索性的分析。本文沒有給出相應計算節點信任度的模型或解決信任安全的機制，而是從信任計算的動力學角度進行了解析研究。根據博弈收益，給出動力學方程，并給出了具體的求解分析，為信任的研究奠定良好的基礎。因此，文中所表達的信任計算不是從量化的角度來衡量信任關系，而是體現在個體進化策略的優化選擇上，通過模仿、試錯等手段，為提高自身的利益，逐漸選擇收益較高且有效穩定的演化策略，從而也保證了整體網絡進化的穩定性和安全性。

1 信任計算的動力學方程

進化博弈論在生物學領域的早期研究是Fisher關于性別比例的研究，在經濟學領域則是Cournot對寡頭市場產量競爭中產量調整過程的研究。Nash對納什均衡的群體行為解釋則是包含較完整的進化博弈思想的最早理論成果。在Maynard Smith和Price引進了進化穩定策略（evolutionarily stable strategy， ESS）概念后，進化博弈論真正受到重視和獲得迅速發展^[12]。

由于有限的知識和局限的認識，從某種意義上講，博弈論所假定的完全理性是不可能存在的，那么有理性局限的參與者稱為有限理性（bounded rationality）的博弈方。有限理性就意味著博弈方之間的策略均衡往往是學習調整的結果。通過試錯、模仿，動態調整策略，在比較穩定的環境中，參與者之間就會形成某種策略的長期穩定趨勢。即使受到少量干擾后仍能恢復到穩健的均衡狀態。

P2P網絡中節點對于其他節點的“無知”就是一種天生的有限理性，這也是由P2P網絡自身的特性所決定的。整個網絡中節點的配對交互（如資源共享）沒有規律可循，具有隨機性。而且對于不同策略，特別是優勢策略的學習調整也是一個漸近的過程，并且所有節點不可能同時調整，這就表現整體節點的學習速度較慢。而在網絡中的交互雙方的信任與不信任就是雙方的有效選擇策略。因此，整個P2P網絡的演化穩定趨勢，即信任策略的動力學方程可以用基于生物自然選擇的進化博弈和生物進化的進化動態方程來分析和表示。

假定節點雙方的有效選擇策略集為｛信任，不信任｝。圖1顯示了一次對稱博弈中博弈雙方的收益矩陣。其中：r為一次博弈中雙方都選擇信任策略時的收益；當一方策略為信任，而另一方的策略為不信任時，s為信任方的收益，d為不信任方的收益，p為雙方都選擇不信任策略時的收益。

在經典的“囚徒困境”中，一次博弈的納什均衡為博弈雙方都選擇不信任策略。但當博弈不限次數地進行下去，博弈雙方在考慮長期收益時，會采用相互信任的策略，這在經濟學的非合作重復博弈理論中被稱為子博弈精練納什均衡^[13]。這樣，將非合作博弈理論引入到P2P網絡，分析解決節點間的信任策略的進化動力，從理論上保證了模型中策略均衡的存在性和網絡進化的穩定性。

按照生物進化復制動態的思想，采用收益低策略的博弈才會通過學習、模仿采用收益高的策略博弈方來逐漸改變自己的策略，因此采用不同策略雙方比例就會慢慢發生改變，某種策略比例的變化速度與其比重和收益超過平均收益的幅度成正比。

假設最初狀態采取信任策略的節點比例為x，則采取不信任策略的節點比例為1-x。

那么，選擇信任策略的節點的期望收益為

u1=xr+(1-x)s(1)

選擇不信任策略的節點的期望收益為

 u2=xd+(1-x)p(2)

整體節點的平均期望收益為

 u=xu1+(1-x)u2(3)

選擇兩種策略的節點的比例不是固定不變的，而是隨著時間變化的。采用信任策略節點的比例的動態變化速度，可以由下列動態微分方程表示：

dx/dt=x(u1-u)(4)

記dx/dt為F(x) ，將式(1)~(3)代入式(4)可得復制動態方程為

dx/dt=F(x)=x(1-x)(x(r-d)+(1-x)(s-p))(5)

要討論該信任博弈的進化穩定策略，應先找出動態復制方程的穩定解。

令F(x)=0，可解得三個復制動態穩定狀態點：

x1=0(7)

 x2=1(8)

 x3=（p-s）/（r-d+p-s）(9)

上述三個解都有可能是進化穩定策略，但根據微分方程的“穩定性原理”可知：穩定狀態處的函數的導數必須小于0，即F′(x)＜0。x表示穩定狀態，也就是進化穩定策略。而在網絡初始狀態兩種策略都可能被選擇，因此要使信任策略成為網絡演化的一個進化穩定策略，r、s、d、p值的設置就是信任計算的動力關鍵所在。

2 信任計算的動力分析

根據上面的方程，下面對于節點的策略選擇，即信任策略的選擇及其動力基礎進行詳細分析。信任策略的選擇，稱之為信任計算，它的動力學基礎主要是由博弈收益矩陣的相應參數所決定，因此，接下來對r、s、d、p四個參數的大小取值進行討論，對信任計算進行詳細的動力分析。

a）當 p＜s，r＜d 且r-d＞p-s時，就會有以下含義：當節點2采用信任策略時，節點1采用不信任策略的得益要大于采用信任策略的得益；當節點2采用不信任策略時，節點1采用信任策略的得益要大于采用不信任策略的得益；反之也是。不難驗證有F′(x1=0)＞0，F′(x2=1)＞0，0＜x3=（p-s）/（r-d+p-s）＜1/2 成立，此時的復制動態微分方程的相位圖如圖2所示。從圖2中可以看出，只有在x=x3處的切線斜率小于0，而x1=0、x2=1 處的切線斜率都大于0。在此，x3是進化穩定策略，而x1、x2 都不是。從圖2中還可以看出，采用信任策略的節點數量最終會穩定在x3左右，采用不信任策略的節點數量為1-x3 ，顯然有1-x3＞ x3。

b）當p＜s ，r＜d且r-d＜p-s時，其含義同情況1。不難驗證有F′(x1=0)＞0，F′(x2=1)＞0 ，1/2＜x3=（p-s)/(r-d+p-s）＜1成立，此時的復制動態微分方程的相位圖如圖3所示。從圖3中同樣可以看出，只有在x=x3處的切線斜率小于0，而x1、x2處的切線斜率都大于0。在此，x3是進化穩定策略，而x1、x2都不是。采用信任策略的節點數量最終會穩定在x3左右，采用不信任策略的節點數量為1-x3 ，顯然有1-x3＜x3。

c）當 p＞s，r＞d且r-d＞p-s時，就會有：當節點2采用信任策略時，節點1采用信任策略的得益要大于不采用信任策略的得益；當節點2采用不信任策略時，節點1采用不信任策略的得益要大于采用信任策略的得益；反之也是。此時，有F′(x1=0)＜0，F′(x2=1)＜0 ， 0＜x3=(p-s)/(r-d+p-s)＜1/2成立，相位圖如圖4所示。可以看出，在x3處的切線斜率大于0，而x1、x2處的切線斜率都小于0。因此，x1、x2是進化穩定策略，而x3不是。信任與不信任兩種策略都有可能被博弈的節點雙方采用，但由于0＜x3=(p-s)/(r-d+p-s)＜1/2，可以看出采用信任策略的概率大于采用不信任策略的概率。

d）當p＞s，r＞d且r-d＜p-s時，其含義同情況3。此時也有F′(x1=0)＜0，F′(x2=1)＜0 ，1/2＜x3=（p-s）/（r-d+p-s）＜1成立，相位圖如圖5所示。同樣可得，采用信任策略的概率小于采用不信任策略的概率。

e）當p＞s，r＜d，此時無論節點1選擇信任或不信任策略，節點2的選擇不信任策略的得益總是大于選擇信任策略的得益。也就是F′(x1=0)＜0，F′(x2=1)＞0時，此時的局部相位圖如圖6所示。可以看出，x1是穩定策略，x2不是，此時的博弈者都傾向采用不信任策略。

f）當p＜s，r＞d，此時無論節點1選擇信任或不信任策略，節點2的選擇信任策略的得益總是大于選擇不信任策略的得益。也就是F′(x1=0)＞0，F′(x2=1)＜0時，此時的局部相位圖如圖7所示。可以看出，x2是穩定策略，x1不是，此時的博弈者都傾向采用信任策略。

由以上分析可以得出，要使信任成為一個進化穩定策略， 理想情況下只有F′(x2=1)＜0。但在一般的情況下，對于博弈雙方的節點來說，采取兩種策略進行博弈是正常的，因此，采用一定的機制來調控，使信任策略逐漸進化為穩定策略，才是網絡安全穩定的關鍵所在。這樣，參數值的設置就顯得舉足輕重了。因此，只要p＜s和r＞d，此時的博弈方都傾向于選擇信任策略，并再有r-d＞＞＞p-s（符號＞＞＞ 的意思是遠大于），縱然最初F′(x1=0)＜0也可能是一個穩定策略，但隨著博弈的進行，此時，由于x3=（p-s）/（r-d+p-s） →0，也就是說通過不斷地試錯、模仿，選擇不信任策略的比例會逐漸降低，最后達到一個穩定的小比例水平。也就會有圖4所示狀態向圖7狀態演化，最終趨于信任策略的穩定，偶爾有少數節點偏離，即采用不信任策略，復制動態會使其回復到穩定水平。這樣，信任成為惟一的進化穩定策略。

通過分析兩種不同策略的信任博弈進化，在不同的激勵和懲罰機制（可以對博弈矩陣中的收益參數進行相應改變）的調節下，信任策略在達到穩定狀態的收斂速度要快于不信任策略。在信任博弈進化過程中，新的博弈策略依賴當前的策略，從一個給定群體狀態達到特定狀態的過程，滿足馬爾可夫性，由于在進化過程中，每一次進化的轉移概率不依賴于時間，該馬爾可夫鏈是齊次的。這進一步說明了策略的進化具有收斂性^[14]，也證實了信任策略最終會成為網絡的進化穩定策略。

3 仿真分析

1）設定 r=10，s=1，p=-1，p-s=-2，對于d=9，d=5，d=1時，dx/dt的變化曲線如圖8所示。當d=9時，r-d=1；d=5時，r-d=5；d=1時，r-d=9。從圖中可以明顯看出，當r-d與p-s的差距越來越大時，dx/dt的變化也非常明顯，也就是說選擇信任策略的比例變化最明顯，調整機制明顯起作用。同樣，只要滿足p＜s和r＞d，并再有r-d＞＞＞p-s，博弈方通過試錯、模仿，不斷調整自己的策略，選擇信任的會越來越多。因此，同理，調整其他的參數值，只要滿足上述條件，也會得到同樣的結果。

2）設定r=10，s=1，p=-1，d=1；r=10，s=-1，p=1，d=1；r=1，s=1，p=-1，d=10；r=1，s=-1，p=1，d=10四組不同的值，分別得到四種不同的變化曲線，如圖9~12所示。在第一種情況中，符合信任作為進化穩定策略的條件，所以，當x比較小時，曲線變化比較快，當x較大時，曲線變化比較緩慢；在第二種情況中，由于當一個節點選擇不信任時，另一節點的最佳策略就是不信任，只有對方采取信任策略時，自己才采取信任策略應對。從圖中看到，曲線的變化是平穩的。在第三種情況下，對方采取信任策略時，自己的對策是不信任，對方采取不信任時，自己的對策是信任，完全是針鋒相對。以及第四種情況，對方選擇信任策略，自己的最佳策略是不信任；對方選擇不信任時，自己的策略還是不信任。從圖中明顯地看出這種策略的選擇，在x達到一定的臨界值之前，dx/dt看不出變化，當達到臨界值后，雖然有函數值的變化，也是非常微小的。因此，x值上看不出什么變化。

從上述的仿真實例中可以得出，對于網絡中節點信任策略的選取，只要采取有效的調控手段，完全可以使信任成為進化的穩定策略，這也為網絡的安全穩定提供了有效機制。從而得出，信任計算的動力學實現要靠參數的調整，也就是說對于網絡中的節點要采取一定的相應激勵措施，獎勵合作、懲罰失信，這才能有利于網絡的穩定進化以及安全。

4 結束語

本文基于進化博弈機理，對P2P網絡中節點的博弈策略選擇，運用復制動態機制分析了其演化趨向，從而進一步分析了信任策略選擇的動力學基礎。可以看出，要使網絡穩定進化，服務性能優化，成為一個可信的網絡環境，可以通過調整博弈交互策略的收益值，以此建立相應的激勵和懲罰機制，使節點之間達到有效合作進化的目的。最終信任策略成為網絡穩定進化、安全服務的有力保障。

在將來的研究工作中，將進一步討論多策略隨機配對進行信任博弈的可行性和可操作性，為網絡的服務優化和整體網絡的穩定性提供可參考模型，完善網絡安全的信任機制，為P2P網絡的穩定進化和服務優化提供更為有力的保證。

參考文獻：

[1]BARAS J S，JIANG Tao . Cooperation， trust and games in wireless networks[C]//Proc of Symposium on Systems， Control and Networks，Honoring Professor P. Varaiya:[s.n.]，2005:183-202.

[2]DOUCEURJ R. The sybil attack[C]//Proc of the 1st International Workshop on Peer-to-Peer Systems (IPTP’02) .2002:251-260.

[3]SUN Y L， HAN Z， YU W，et al.Attacks on trust evaluation in distributed networks[C]//Proc of the 40th Annual Conference on Information Sciences and Systems.2006.

[4]ADARE，HUBERMAN B A. Free riding on Gnutella，SSL-00-63 [R]. Palo Alto: Xerox PARC， 2000.

[5]KAMVAR S D， SCHLOSSER M T， MOLINAH G. The eigentrust algorithm for reputation management in P2P networks[C]//Proc of the 12th International Conference on World Wide Web.[S.l.]:ACM Press， 2003:640-651.

[6]KAMVAR S D， SCHLOSSER M T， MOLINAH G. EigenRep:reputation management in P2P networks[C]//Proc of the 12th International World Wide Web Conference.Budapest: ACM Press， 2003:123-134.

[7]XIONG L， LIU L. A reputation-based trust model for peer-to-peer e-commerce communities[C]//Proc of IEEE Conf on E-Commerce (CEC’03).Newport Beach， California:[s.n.]，2003.

[8]STOICAI， MORRISR， KARGERD， et al.Chord:a scalable peer-to-peer lookup service for Internet applications[C]//Proc of the ACM SIGCOMM 2001.San Diego:[s.n.]，2001.

[9]ABERER B.P-Grid:a self organizing access structure for P2P information systems [C]//Proc of the 6th International Conference on Cooperative Information Systems.2001:179-194.

[10]SZTOMPKA P. Trust: a sociological theory [M].Cambridge:Cambridge University Press， 1999.

[11]ALCHIANA. Uncertainty， evolution， and the economic theory [J]. The Journal of Political Economy， 1995，58(3):211-221.

[12]謝識予. 有限理性條件下的進化博弈理論[J]. 上海財經大學學報， 2001，3(5):3-9.

[13]MYERSON R B. Game theory: analysis of conflict [M].Massachusetts:Harvard University Press， 1991.

[14]丁建中， 陳增強， 袁著祉. 遺傳算法與螞蟻算法融合的馬爾可夫收斂性分析[J]. 自動化學報， 2004， 30(4):629-634.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文