基于進(jìn)化博弈的Ｐ２Ｐ網(wǎng)絡(luò)中信任計算的動力學(xué)分析

摘 要：運用動力學(xué)原理，基于進(jìn)化博弈理論，對信任計算的動力學(xué)方程進(jìn)行了求解分析，并運用復(fù)制動態(tài)原理分析了節(jié)點之間信任關(guān)系的演化趨勢，進(jìn)一步揭示了信任計算的演化動力學(xué)規(guī)律。仿真實驗表明，進(jìn)化是網(wǎng)絡(luò)節(jié)點信任合作的動力源泉。

關(guān)鍵詞：點對點網(wǎng)絡(luò);信任計算;進(jìn)化博弈;復(fù)制動態(tài)

中圖分類號：TP393 文獻(xiàn)標(biāo)志碼：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網(wǎng)絡(luò)安全中的一個重要概念，是網(wǎng)絡(luò)節(jié)點之間關(guān)系的集合^[1]。但在P2P網(wǎng)絡(luò)中，沒有中心服務(wù)器和可信第三方提供擔(dān)保，這種關(guān)系的建立相當(dāng)困難。因為用來評價信任的信息或證據(jù)有著非完整性、不確定性等特點。又因為P2P網(wǎng)絡(luò)的開放性、匿名性、自治性等，網(wǎng)絡(luò)中存在相當(dāng)數(shù)量的惡意節(jié)點和自私節(jié)點，如傳播Sybil^[2]、Bad Mouthing、On-off^[3]等攻擊的節(jié)點以及大量的Free-Riders^[4]節(jié)點。這些節(jié)點的存在嚴(yán)重影響了整體網(wǎng)絡(luò)的性能，破壞了網(wǎng)絡(luò)系統(tǒng)的安全性和穩(wěn)定性。因此，建立適當(dāng)?shù)陌踩湃螜C制，促進(jìn)節(jié)點間信任合作，激勵誠信、懲罰失信是很有必要的。

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

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

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

1 信任計算的動力學(xué)方程

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

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

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

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

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

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

假設(shè)最初狀態(tài)采取信任策略的節(jié)點比例為x，則采取不信任策略的節(jié)點比例為1-x。

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

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

選擇不信任策略的節(jié)點的期望收益為

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

整體節(jié)點的平均期望收益為

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

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

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

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

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

要討論該信任博弈的進(jìn)化穩(wěn)定策略，應(yīng)先找出動態(tài)復(fù)制方程的穩(wěn)定解。

令F(x)=0，可解得三個復(fù)制動態(tài)穩(wěn)定狀態(tài)點：

x1=0(7)

 x2=1(8)

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

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

2 信任計算的動力分析

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

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

b）當(dāng)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成立，此時的復(fù)制動態(tài)微分方程的相位圖如圖3所示。從圖3中同樣可以看出，只有在x=x3處的切線斜率小于0，而x1、x2處的切線斜率都大于0。在此，x3是進(jìn)化穩(wěn)定策略，而x1、x2都不是。采用信任策略的節(jié)點數(shù)量最終會穩(wěn)定在x3左右，采用不信任策略的節(jié)點數(shù)量為1-x3 ，顯然有1-x3＜x3。

c）當(dāng) p＞s，r＞d且r-d＞p-s時，就會有：當(dāng)節(jié)點2采用信任策略時，節(jié)點1采用信任策略的得益要大于不采用信任策略的得益；當(dāng)節(jié)點2采用不信任策略時，節(jié)點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是進(jìn)化穩(wěn)定策略，而x3不是。信任與不信任兩種策略都有可能被博弈的節(jié)點雙方采用，但由于0＜x3=(p-s)/(r-d+p-s)＜1/2，可以看出采用信任策略的概率大于采用不信任策略的概率。

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

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

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

通過分析兩種不同策略的信任博弈進(jìn)化，在不同的激勵和懲罰機制（可以對博弈矩陣中的收益參數(shù)進(jìn)行相應(yīng)改變）的調(diào)節(jié)下，信任策略在達(dá)到穩(wěn)定狀態(tài)的收斂速度要快于不信任策略。在信任博弈進(jìn)化過程中，新的博弈策略依賴當(dāng)前的策略，從一個給定群體狀態(tài)達(dá)到特定狀態(tài)的過程，滿足馬爾可夫性，由于在進(jìn)化過程中，每一次進(jìn)化的轉(zhuǎn)移概率不依賴于時間，該馬爾可夫鏈?zhǔn)驱R次的。這進(jìn)一步說明了策略的進(jìn)化具有收斂性^[14]，也證實了信任策略最終會成為網(wǎng)絡(luò)的進(jìn)化穩(wěn)定策略。

3 仿真分析

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

2）設(shè)定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所示。在第一種情況中，符合信任作為進(jìn)化穩(wěn)定策略的條件，所以，當(dāng)x比較小時，曲線變化比較快，當(dāng)x較大時，曲線變化比較緩慢；在第二種情況中，由于當(dāng)一個節(jié)點選擇不信任時，另一節(jié)點的最佳策略就是不信任，只有對方采取信任策略時，自己才采取信任策略應(yīng)對。從圖中看到，曲線的變化是平穩(wěn)的。在第三種情況下，對方采取信任策略時，自己的對策是不信任，對方采取不信任時，自己的對策是信任，完全是針鋒相對。以及第四種情況，對方選擇信任策略，自己的最佳策略是不信任；對方選擇不信任時，自己的策略還是不信任。從圖中明顯地看出這種策略的選擇，在x達(dá)到一定的臨界值之前，dx/dt看不出變化，當(dāng)達(dá)到臨界值后，雖然有函數(shù)值的變化，也是非常微小的。因此，x值上看不出什么變化。

從上述的仿真實例中可以得出，對于網(wǎng)絡(luò)中節(jié)點信任策略的選取，只要采取有效的調(diào)控手段，完全可以使信任成為進(jìn)化的穩(wěn)定策略，這也為網(wǎng)絡(luò)的安全穩(wěn)定提供了有效機制。從而得出，信任計算的動力學(xué)實現(xiàn)要靠參數(shù)的調(diào)整，也就是說對于網(wǎng)絡(luò)中的節(jié)點要采取一定的相應(yīng)激勵措施，獎勵合作、懲罰失信，這才能有利于網(wǎng)絡(luò)的穩(wěn)定進(jìn)化以及安全。

4 結(jié)束語

本文基于進(jìn)化博弈機理，對P2P網(wǎng)絡(luò)中節(jié)點的博弈策略選擇，運用復(fù)制動態(tài)機制分析了其演化趨向，從而進(jìn)一步分析了信任策略選擇的動力學(xué)基礎(chǔ)。可以看出，要使網(wǎng)絡(luò)穩(wěn)定進(jìn)化，服務(wù)性能優(yōu)化，成為一個可信的網(wǎng)絡(luò)環(huán)境，可以通過調(diào)整博弈交互策略的收益值，以此建立相應(yīng)的激勵和懲罰機制，使節(jié)點之間達(dá)到有效合作進(jìn)化的目的。最終信任策略成為網(wǎng)絡(luò)穩(wěn)定進(jìn)化、安全服務(wù)的有力保障。

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

參考文獻(xiàn)：

[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ìn)化博弈理論[J]. 上海財經(jīng)大學(xué)學(xué)報， 2001，3(5):3-9.

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

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

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