一種Ｐ２Ｐ文件共享系統中的激勵機制
2009-01-01 00:00:00莊雷常玉存董西廣
計算機應用研究 2009年1期
（鄭州大學 信息工程學院， 鄭州450052）
摘 要：提出了一種用于文件共享系統的激勵機制，將節點享受服務的能力和提供服務的能力進行區分，貢獻節點享有更高的服務優先級，而搭便車節點受到懲罰。仿真實驗表明，該激勵機制充分體現了公平性原則，同時大大提高了下載成功率。
關鍵詞：對等網絡；搭便車；污染；激勵機制
中圖分類號：TP393 文獻標志碼：A
文章編號：10013695(2009)01026603
Incentive mechanism in peertopeer file sharing system
ZHUANG Lei，CHANG Yucun，DONG Xiguang
(School of Information Engineering， Zhengzhou University， Zhengzhou 450052， China)
Abstract:This paper presented a new incentive mechanism which could be applied to the file sharing systems， the ablity of the user to enjoy service was distinguished from the ability to provide service， contributing nodes had more preference to get services.In contrast， freeriders were punishied.The simulation results show that the incentive mechanism fully embodies the fairness principles， meanwhile greatly improves the success rate of downloading.
Key words:peer to peer(P2P) network; freeriding; pollution; incentive mechanism
0 引言
P2P網絡是一種開放、匿名的網絡，所有節點均是對等的，每個節點既是服務的提供者，也是服務的接受者。P2P網絡具有負載均衡、資源豐富等優點，目前已獲得廣泛應用。然而，節點由于固有的理性均希望最大化自己的利益和效用，從而導致了節點只想索取資源而不愿貢獻資源的行為[1，2]。P2P網絡中大量節點作出這種選擇的結果將導致P2P網絡效用大幅降低，絕大多數節點均無法得到正常的服務，類似情況也普遍存在于其他P2P應用系統中。文獻[1]將節點只享受資源服務而不為系統做貢獻的行為稱為搭便車(freeriding)。顯然，搭便車現象與P2P通信模式提倡的協做共享理念不一致，大量的搭便車行為會降低對等網絡的性能，增加系統的脆弱性。如果搭便車現象進一步加劇，可能會導致整個P2P應用系統最終崩潰。因此，必須對搭便車行為進行有效的抑制。
P2P文件共享應用的普及也引起了污染（pollution）行為[3]，這是指電影音樂界為了防止大量有版權影音文件的傳遞采取的一種技術手段，即為了將具有版權的內容變得不能使用而竄改其內容，同時將竄改過的大量文件投放到文件共享網絡中，從而造成污染。其目的是欺騙用戶經常下載被感染的文件，使用戶對下載變得失望而離開文件共享系統。
本文在現有研究的基礎上，提出了一種新型激勵機制，它具有如下優點：a）將節點享受服務的能力(TRclient)和提供服務的能力(TRserver)區分開來， TRclient體現了公平性原則，通過TRserver則大大提高了下載成功率。b）通過TRclient將客戶節點分為三個等級，由服務節點來進行區分服務。貢獻節點享有更高的服務優先級，而搭便車節點受到懲罰，從而吸引用戶做出貢獻。c）惡意節點進行欺詐、pollution行為將導致節點TRserver降低，節點提供的服務將不被其他客戶節點接受，從而實現了對惡意節點的隔離。d）算法比較簡單，工程可行性很好。e）無論是交易頻繁或是交易稀少的網絡，只要適當系統參數，均會有很好的適應性，從而提高了系統的靈活性。
1 相關工作
針對上述問題，人們研究了P2P系統中公平性和信譽度維護方案，公平性一般不考慮服務質量，如文獻[4]僅僅以傳輸文件次數表征系統公平性；文獻[5]使用博弈論觀點討論了如何根據公平性指數對用戶提供區分服務；文獻[6，7]中提出了采用社會經濟生活中審計、競價等機制抑制搭便車行為；文獻[8]對freeriding和whitewashing現象進行了數學分析。但是由于網絡中總是存在一定數量的惡意節點，這類節點隨機做出虛假有害的行為，如抵賴服務、pollution行為等，因此必須引入信任(trust)機制來保證P2P系統的服務效用，基本思想是每個用戶有一個信任度，客戶節點選擇較高信任度的服務節點來獲取服務，從而降低被欺騙的可能，交易過后，客戶節點對交易進行評價，系統根據交易評價來更新服務節點的信任度。Vishnumurthy等人[9]給出了一種結構化P2P中信任度維護方案，此外，大量研究討論分布式系統中trust維護和計算，文獻[10，11]均在某些方面作了改進。
上述模型各有其優點，但是并沒有同時考慮公平性和服務質量，因此需要一種機制在抑制搭便車行為的同時，來提高服務的質量。 文件共享系統中，存在大量的搭便車和污染行為，本文提出的激勵機制，既對搭便車行為進行了抑制，同時也對污染節點進行了識別，充分體現了公平性和效率的統一。
2 激勵機制
21 基本概念和說明
a）信譽(trust)。表征節點享受服務或提供服務的能力大小，本文中，trust為一實數值且∈[-1，1]。
b）時間距離計算信譽度的時刻越遠，節點行為對信譽度的影響越小。這種現象稱為時間衰減效應，其強度可以用時間衰減因子σ表示。0≤σ≤1，σ值越大，時間衰減效應越小。當σ=1時，時間衰減效應為0，σ通常取0.8～1的常數。
c）選取一個合適的時間段作為整個交易歷史時間跨度中的一個評價周期EP，可以將整個交易歷史劃分為若干個EP。通常只考慮最近的N個EP內的節點行為。當用戶的生存期不足N個EP時，向前擴充為N個EP，擴充EP對應的貢獻表和索取表的項均為0。通常N取值為[10，30]。
d）網絡中的每個節點需要維護兩個表，一個是貢獻表CT(Q1，Q2，Q3，…，Qn，Qn+1)，表中前N項分別記錄最近N個EP(依次為EP1，EP2，EP3，…)的節點貢獻，最后一項是節點當前EP的貢獻；一個是索取表DT（R1，R2，R3，…，Rn，Rn+1），此表記錄前N項分別記錄最近N個EP的節點索取，最后一項為節點當前EP的索取。每個表的大小均為N+1。
22 信譽度更新
本文的設計思想為：每個節點含有兩個trust，分別用TRclient和TRserver表示。
a）TRclient。它僅用來獲取服務，為了激勵節點向系統做出貢獻，在2.3節設計了一個激勵算法，將TRclient分為三個層次，各個層次享受服務的優先級也各不相同。節點向系統提供的貢獻越多，TRclient越高，而節點索取得越多，則TRclient越低。在此，采用節點向其他節點提供的下載量來表示TRclient，節點向其他節點提供文件下載，則引起TRclient的增加；反之，節點若僅僅進行大量的下載，則引起TRclient的減少。TRclient計算公式如下：
TRclient=ni=1infi(u)×σi/ni=1σi(1)
其中：1≤i≤n，infi(u)為節點u在EPi內累積的信譽度：
infi(u)=1(Qi-Ri)/λ≥1
-1(Qi-Ri)/λ≤-1
(Qi-Ri)/λ其他
其中：λ為貢獻閾值，在文件共享系統中，λ通常取為上傳文件的字節數，節點提供大的文件TRclient上升較快。
b）TRserver。它僅用來提供服務，當客戶節點S發出交易請求時，通常會有多個服務節點響應，這時，S選擇TRserver值較大的節點進行交易。服務節點的TRserver與其提供的服務質量有關，服務節點提供服務且客戶節點滿意時，TRserver增加，本文引入交易評價，當客戶節點S與服務節點U交易完畢以后，S對U提供的服務進行評價，評價值sat∈{-1，1}。其中：-1、1分別表示S對U的服務不滿意、滿意。
TRserver=ni=1sati(u)×Mi/
ni=1Mi(2)
其中：sati(u)為第i次交易中，u獲取的交易評價，Mi為u提供的文件大小。提供大文件且客戶節點滿意，則信譽值上升較快；而提供大文件但客戶節點不滿意(如pollution文件)，則引起信譽度較快下降。
當S與U交易完畢(文件大小為M)以后，S對U提供的交易評價為E。U修改其當前EP對應CT表項Qn+1為Qn+1+E×M，而S修改當前EP對應DT表項Rn+1為Rn+1+M。當前EP結束以后，進入下一個EP，CT和DT表項均向左平移，Qn+1復位為0。若交易跨越了多個EP，則以交易完成時的EP為準。
23 懲罰和激勵
在P2P網絡中，貢獻者和搭便車者所處的地位是不平等的，為了體現公平性原則，貢獻者應該受到更多的重視。筆者通過兩個信譽閾值參數τmax和τmin，將TRclient分為三個等級：a)當TRclient＞τmax時，在過去的N個時段內，相對于索取節點進行了更多的貢獻。b)當τmin≤TRclient≤τmax時，用戶在過去的N個時段內，索取與貢獻基本持平或者沒有任何行為。c)當TRclient<τmin時，此類用戶在過去的N個時段內基本上沒有做出有效的貢獻，但卻進行了大量的索取，信譽度下降到τmin以下。c)類用戶的行為屬于搭便車行為，應該受到抑制。而a)類用戶的行為是貢獻行為，應該受到鼓勵。τmax和τmin可以根據不同的應用環境靈活設置，如τmin=0，τmax=0.5。
本文提出的激勵機制中，網絡中的每個節點均有三個服務隊列（分別為q1，q2，q3），優先級分別為p1，p2，p3，且p1>p2>p3。設網絡中節點保持的最大連接數為M，客戶節點U首先發出資源查詢請求（U，F），服務節點首先根據U的TRclient來決定是否響應，具體響應算法如下：
Response algorithm
begin
S對節點U的信譽度TRclient進行計算
if(TRclient>τmax) S響應(U，F)
elseif(τmin<=TRclient<=τmax)
S以概率ψ1響應(U，F)
else S以概率ψ2響應(U，F)
end
算法中概率函數ψ1=1-e-λ/f#8226;TRclient，ψ2=1-e-TRclient，f為文件F的大小。由于b)類節點并沒有表現出明顯的搭便車行為，因此，增加了一個文件大小參數，即當其請求的數據量較小時，服務節點仍以較高的概率進行響應。
當一個服務節點S(擁有文件F)響應客戶節點U的資源下載請求(U，F)后，執行如下激勵算法：
Incentivealgorithm
begin:
if(TRclient>τmax)
S按照TRclient有序將(U，F)插入q1隊列中
else if(τmin<=TRclient<=τmax)
S將(U，F)插入到q2隊列末尾
else
S將(U，F)插入到q3隊列末尾
if(q1隊列非空下載連接數量 S按照FCFS策略為q1隊列中的用戶服務 else if(q2隊列非空下載連接數量 S按照FCFS策略為q2隊列中的用戶服務 else if(q3隊列非空下載連接數量 S按照FCFS策略為q3隊列中的用戶服務 end 24 激勵機制分析 a）在P2P系統中，每個節點地位平等，既充當服務器，為其他節點提供服務，又充當客戶機，從其他節點獲取服務，而節點提供服務和享受服務的能力并不對稱，因此，將其區分是很有必要的。本文中，每個節點有兩個信譽，即TRclient、TRserver，分別代表節點享受服務的能力和提供服務的能力。 b）搭便車節點只希望從系統索取資源而不向系統做出貢獻，因此搭便車節點的TRclient較低。當服務節點根據客戶節點的TRclient給予不同層次的服務時，搭便車者將具有較低的下載優先級，而且筆者提供了一個概率函數，服務節點可以一定的概率來拒絕搭便車者的請求。而貢獻節點的TRclient較高，因此，享有較高的下載優先級和服務質量。 c）當一些欺騙節點提供一些經過惡意竄改，甚至包含病毒、惡意代碼等內容的文件下載時，客戶節點可以提供較低的交易評價，從而使這些節點的TRserver降低，由于客戶節點通常選取TRserver較高的服務節點獲取服務，欺騙節點提供的服務將不被接受，這又會使得欺騙節點的TRclient值減小，即享受服務的能力降低，這些節點將最終被隔離出P2P系統。 d）計算TRclient時，充分考慮了時間因素的影響，通常近期的行為更能反映節點的狀態，因此近期節點的交易在計算信譽度時占有更高的權重。時間衰減因子的引入，使得信譽度的計算更加合理。 3 實驗模擬 筆者構造了多個仿真實驗來檢測模型。實驗規模包括1 000個節點，應用場景是文件共享服務，文件總數為10 000個，文件的分布滿足Zipf定律。節點包括貢獻節點、搭便車節點和欺騙節點。欺騙節點提供大量的pollution文件服務。設每個節點平均完成100次交易，每次交易目標為從其不曾擁有的文件中隨機選擇一個并試圖進行下載。交易成功的標準是文件的真實性，交易的成功使得該用戶擁有該文件，失敗的交易不會增加該用戶擁有的文件。在這里，仍然假定文件共享網絡是理想的，即任意用戶可以找到任意文件及其聲稱為該文件擁有者的所有節點。 實驗中對比了不同規模（0~50%）的欺騙節點對引入了該激勵機制的P2P系統和沒有引入任何激勵機制的P2P系統的影響，結果如圖1所示。從圖中可以看出，隨著欺騙節點比例的增加，引入該激勵機制的下載成功率仍然能維持在一個較高水平，即使欺騙節點達到50％，其下載成功率仍然達50％以上，而沒有引入任何激勵機制的P2P系統其下載成功率為30%以下。由此可見，該機制有效地隔離了pollution行為，提高了系統的下載成功率。 同時筆者比較了激勵機制對貢獻節點和搭便車節點TRclient的影響。圖2是貢獻節點的平均TRclient變化情況。可以看出，節點由于做出了大量的貢獻使TRclient快速增加，從而享有更高的服務質量和下載優先級。圖3是搭便車節點的平均TRclient變化情況。由于搭便車節點只進行大量索取而幾乎不做出貢獻，TRclient迅速下降，從而享有較低的優先級和服務質量。 4 結束語 針對P2P文件共享中存在的大量搭便車和污染現象，本文提出了一種新型激勵機制。通過TRclient來抑制搭便車現象，而TRserver可以避免一些欺騙節點的pollution行為。仿真實驗表明，該激勵機制保證了較高的下載成功率，同時鼓勵了貢獻節點，懲罰了搭便車行為。 這種將用戶提供服務和獲取服務能力進行區分的思想可以應用于其他P2P系統中。此時的TRclient和TRserver如何量化，以及信譽度的分布式維護等都是下一步要研究解決的問題。 參考文獻： ［1］ ADAR E，HUBERMAN B A.Freeriding on Gnutella[J].First Monday，2000，5(10):4268. ［2］ HUGHES D，COULSON G，WALKERDINE J.Freeriding on Gnutella revisited:the bell tolls[J].IEEE Distributed Systems Online，2005，6(6):118. ［3］ LIANG J，KUMAR R，XI Y，et al.Pollution in P2P file sharing systems[C]//Proc of IEEE Infocom.Miami:[s.n.]，2005. ［4］ KUNG H T，WU C H.Differentiated admission for peertopeer systems:incentivizing peers to contribute their resources[EB/OL].(20031221)[20050303].http://www2.sims.berkeley.edu/research/conferences/p2pecon/papers/s5kung.pdf. ［5］MA R T B，LEE S C M，LUI J C S，et al.A game theoretic approach to provide incentive and service differentiation in P2P networks[J].ACMSigmetrics Performance Evaluation Review，2004，32(1):189198. ［6］LANG K T，VRAGOV R.A pricing mechanism for digital content distribution over peertopeer networks[C]//Proc of the 38th Annual Hawaii International Conference on System Sciences.Hawaii:[s.n.]，2005. ［7］HALES D，EDMONDS B.Applying a socially inspired technique(tags) to improve cooperation in P2P networks[J].IEEE Trans on System:System and Humans，2005，35(3):385395. ［8］FELDMAN M，CHRISTOS P，CHUANG J，et al.Freeriding and whitewashing in peertopeer systems[J].IEEE Trans on System，Man and Cybernetics，2006，24(5):228236. ［9］VISHNUMURTHY V，CHANDRAKUMAR S，SIRER E G.KARMA:a secure economic framework for peertopeer resource sharing[EB/OL].(20030819)[20050303].http://www.cs.cornell.edu/people/egs/papers/karma.pdf. ［10］XIONG L，LIU L.A reputationbased trust model for peertopeer Ecommerce communities[C]//Proc of IEEE Conference on Ecommerce.California:ACM Press，2003:228229. ［11］ 竇文，王懷民，賈焰，等.構造基于推薦的peertopeer環境下的trust 模型[J].軟件學報， 2004，15(4):571583.
