P2P網(wǎng)絡(luò)中基于信任的拓?fù)浣Y(jié)構(gòu)與搜索機制

魏長明

(低維量子結(jié)構(gòu)與調(diào)控教育部重點實驗室，湖南師范大學(xué)物理與信息科學(xué)學(xué)院，中國 長沙 410081)

有關(guān)數(shù)據(jù)表明P2P通信流量已經(jīng)在Internet通信總量中占到了相當(dāng)巨大的比例[1]．在P2P系統(tǒng)中，用戶節(jié)點既可作為客戶機，又可作為服務(wù)器，它是當(dāng)前的大規(guī)模分布式資源共享系統(tǒng)．資源搜索是節(jié)點在網(wǎng)絡(luò)中查尋合適的信息提供者的過程，其首先需要定位相應(yīng)的資源提供者，因此提高系統(tǒng)的資源查找效率十分關(guān)鍵．

根據(jù)數(shù)據(jù)的存儲分配和網(wǎng)絡(luò)拓?fù)?，P2P系統(tǒng)可以分為兩大類：結(jié)構(gòu)化的和非結(jié)構(gòu)化的[2]．較早的研究已經(jīng)表明了結(jié)構(gòu)化P2P系統(tǒng)可以有效地改進(jìn)系統(tǒng)的性能，如CAN、Tapstry和Chord[3]等.然而，結(jié)構(gòu)化P2P系統(tǒng)的嚴(yán)格結(jié)構(gòu)使得網(wǎng)絡(luò)很難擴展和維護(hù)，動態(tài)性很差．非結(jié)構(gòu)化P2P系統(tǒng)是完全自組織分布式的，資源可以隨機地分配到任意節(jié)點上，如文獻(xiàn)[4]提出了一種基于“gossip”的非結(jié)構(gòu)化P2P系統(tǒng)的資源搜索機制.但是，它們往往搜索效率低下．有關(guān)研究表明，借鑒人類社會社區(qū)的概念之上虛擬社區(qū)方法有助于提高資源共享和發(fā)現(xiàn)的效率[5]．節(jié)點通過更新同其他節(jié)點的鏈接關(guān)系來實現(xiàn)自組織的目的，節(jié)點以完全分布的方式來更新同其他節(jié)點的關(guān)系，使節(jié)點在拓?fù)渖媳憩F(xiàn)為虛擬社區(qū)形式的聚集[6]．基于興趣的聚集是目前拓?fù)溲芯康臒狳c，其假定了網(wǎng)絡(luò)中節(jié)點的交互圍繞著一定的興趣偏好，此類聚集方案都是通過度量節(jié)點間共享資源內(nèi)容的相似性來更新鏈接關(guān)系，并利用節(jié)點的聚集效應(yīng)降低網(wǎng)絡(luò)直徑、削減網(wǎng)絡(luò)流量、改善資源發(fā)現(xiàn)效率等[7]．實際上這類方案都是基于如下假設(shè)：具有相近興趣的節(jié)點更能提供所需的服務(wù)．其中存在的主要問題是基于興趣的自組織方案沒有考慮節(jié)點實際提供服務(wù)的能力，即使一個節(jié)點具有相同的興趣，但并不意味著都可以提供較好的服務(wù)質(zhì)量．

目前，P2P系統(tǒng)中關(guān)于信任研究和應(yīng)用已經(jīng)涉及到了基于節(jié)點可信性的拓?fù)溥M(jìn)化問題，其中使用信任來刻畫節(jié)點提供服務(wù)的能力可以依據(jù)節(jié)點在網(wǎng)絡(luò)中的活動狀態(tài)來更新同它的交互關(guān)系，相應(yīng)地改善網(wǎng)絡(luò)性能．本文提出了一種基于信任的拓?fù)浣Y(jié)構(gòu)和資源搜索機制．首先，描述了信任計算模型，然后，對網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和搜索機制進(jìn)行了詳細(xì)的闡述，最后通過仿真實驗檢驗了該機制的有效性．

1 信任計算

信任是主體對客體特定行為的主觀可能性預(yù)期；對這個期望可以用信任度來衡量，信任度取決于一個被信任實體完成任務(wù)的能力、誠實度、可靠性等．在P2P網(wǎng)絡(luò)中提供服務(wù)的節(jié)點稱為服務(wù)節(jié)點，享受服務(wù)的節(jié)點稱為消費節(jié)點．為了便于區(qū)分善惡節(jié)點，每個節(jié)點必須被賦予一定的可信度．消費節(jié)點優(yōu)先選擇信任值高的服務(wù)節(jié)點進(jìn)行交易．而服務(wù)節(jié)點可以根據(jù)一定的訪問控制策略接受高信任值節(jié)點的請求和拒絕低信任值節(jié)點的請求．所以，每個節(jié)點應(yīng)該爭取提升自己信任值，以獲取更好的服務(wù)．節(jié)點可以通過為別的節(jié)點提供優(yōu)質(zhì)可靠的服務(wù)來提高自己信任值．當(dāng)然如果節(jié)點提供虛假文件下載或服務(wù)質(zhì)量低，其信任值應(yīng)該被降低以懲罰．把P2P網(wǎng)絡(luò)中進(jìn)行的一次消費與服務(wù)稱為交易，消費節(jié)點可以對該次交易進(jìn)行評價．交易評價值是消費節(jié)點對服務(wù)節(jié)點的服務(wù)質(zhì)量的數(shù)量評價，它將影響服務(wù)節(jié)點信任值的高低．

因為信任的本質(zhì)使得信任很難用一個精確的值來表示，因此在這里，信任度的值用[-1,1]之間的實數(shù)來表示．很多信任計算模型中使用滿意的或不滿意的交易次數(shù)來計算信任值[8]．而實際情況是，僅僅使用“滿意”和“不滿意”來評價一次交易是不夠精確的．該信任計算模型使用多種評價值以提高信任值的計算精度．以4種評價值為例，各種取值情況如表1 所示．實際應(yīng)用時，根據(jù)具體的情況還可對評價值進(jìn)一步細(xì)化．

表1 評價說明

由于本文的重點不在于對信任計算模型的研究，所以只給出一個信任計算的簡單模型，需要深入研究的有關(guān)讀者可以參考文獻(xiàn)[8～9]等．

首先給出節(jié)點s的信任度基本計算公式：

TS=σTSC+E(s,i)

(1)

其中，TSC為第i次交易之前節(jié)點s的信任度，其初始值為0，TS第i次交易之后節(jié)點s的信任度；E(s,i)代表與節(jié)點s進(jìn)行第i次交易后的交易評價值，其取值范圍為(-1, 1)，如表1所示，具體大小由交易請求者對服務(wù)的滿意程度決定；信任σ為時間衰減因子，其取值范圍為(0, 1)．

在網(wǎng)絡(luò)中發(fā)生的成千上萬的交易中，每次交易都是和其他交易有不一樣的地方，并不能夠平等看待它們的重要級別．比如有的交易的規(guī)模很大，有的交易的重要性很高，有的交易的持續(xù)時間很長等等．這都是造成每次交易的權(quán)重不盡相同的原因．例如一個作電子商務(wù)的社區(qū)，那么在計算針對某次交易的反饋值的時候，那次交易的交易額就是非常重要的考慮因素．于是我們引入交易環(huán)境因子來調(diào)整公式(1)，從而成功地阻止某些節(jié)點想要進(jìn)行某些惡意行為的企圖．比如上面我們提到過的，某個節(jié)點可能在參與許多次交易額比較小的事務(wù)時，遵守規(guī)則，表現(xiàn)良好，但是在參與交易額很大的事務(wù)時，因為有利可圖，為了給自己獲得最大的利潤，它可能就利用自己以前在許多小型交易中積累的良好的信譽去欺騙另外的交易一方，從中獲利．也就是說應(yīng)該考慮交易的內(nèi)容以及它的范圍．

因此，作者引入交易環(huán)境因子來調(diào)整信任度計算公式．

TS=σTSC+E(s,i)×H(s,i)

(2)

其中H(s,i)為交易環(huán)境因子，表示節(jié)點s第i次交易的權(quán)重，具體大小與交易的種類、時間長短、規(guī)模等有關(guān)．

2 網(wǎng)絡(luò)拓?fù)浜退阉鳈C制

2.1 網(wǎng)絡(luò)拓?fù)錁?gòu)建

定義1有向圖G=(P，E)，其中P是節(jié)點集合，E是邊的集合，(i，j)∈E，表示了節(jié)點i到j(luò)的鏈接，(i，j)∈P．

P2P網(wǎng)絡(luò)可以表示為一個有向圖G，P2P網(wǎng)絡(luò)中的鏈接是非對稱的，代表了節(jié)點的資源查詢消息的轉(zhuǎn)發(fā)通道．

定義2稱N(i)={j|(i,j)∈E}為節(jié)點i的直接鄰居節(jié)點集合，即節(jié)點i可將查詢消息轉(zhuǎn)發(fā)到的直接鄰居節(jié)點．

為了實現(xiàn)同服務(wù)提供能力較強、信任度高的節(jié)點間的連接關(guān)系．一般，選取最近與節(jié)點i有過交易并且服務(wù)提供能力較強、信任度高的節(jié)點構(gòu)成集合Ni．

那么，P2P網(wǎng)絡(luò)拓?fù)溆邢驁DG有如下幾個屬性：

(1)隨著節(jié)點動態(tài)的加入和退出，以及節(jié)點對直接鄰居節(jié)點的選擇都會導(dǎo)致節(jié)點間的鏈接的更新，網(wǎng)絡(luò)拓?fù)溆邢驁DG會隨時間而改變；

(2)由于沒有全局知識，節(jié)點利用本地對其他節(jié)點的知識對直接鄰居節(jié)點的選擇可能導(dǎo)致節(jié)點的聚集；

(3)節(jié)點鏈接更新算法應(yīng)該考慮節(jié)點間信息的分發(fā)．

P2P系統(tǒng)中每個節(jié)點都保有一張以往的交易對象列表和直接鄰居節(jié)點列表，其中交易對象列表包括交易節(jié)點身份、相應(yīng)的信任值以及該信任值更新時間，直接鄰居節(jié)點列表包括直接鄰居節(jié)點身份信息、相應(yīng)的身份值以及該信任值更新時間．兩個列表中的每一記錄的時間都必須是最近的，可以規(guī)定一個時限(比如1個月)，超過時限的信任值記錄，節(jié)點可以周期性的更新本地直接鄰居列表以及相應(yīng)的信任值記錄．

定義3記Tj為i對j的信任值．

定義4稱Mi為節(jié)點i有其信任記錄的節(jié)點集合．

隨著關(guān)于特定目標(biāo)節(jié)點的交互經(jīng)驗的積累，以及目標(biāo)節(jié)點行為的變化等因素，都將導(dǎo)致對目標(biāo)節(jié)點信任判斷的更新，相應(yīng)的，也需要更新鏈接以反映信任因素的變化．這里給出了一個基于信任鏈接更新算法，使網(wǎng)絡(luò)中的節(jié)點同具有更強的服務(wù)能力的節(jié)點建立更為緊密的交互關(guān)系．在i與目標(biāo)節(jié)點j交易完成，通過公式(2)計算獲得節(jié)點j的信任值Tj后，若j∈Mi-Ni，Ni中h的信任值最小，且Tj>Th，則用j的鏈接替換同h的鏈接；若j∈Ni，Mi-Ni中h的信任值最大，且Th>Tj，則用h的鏈接替換同j的鏈接．節(jié)點i的鏈接更新算法偽代碼如下算法1：

updateTrust(j)

if |N|<Φthen

connectTo(j);

else

ifj∈Mi-Nithen

h=chooseNodeWithMinTrustFrom(Ni);

ifTh

connectionReplaceWith(h,j);

endif

else

h=chooseNodeWithMaxTrustFrom(Mi-Ni);

ifTh>Tjthen

connectionReplaceWith(j,h);

endif

endif

endif

算法1鏈接更新算法

這里的updateTrust()過程指的是，當(dāng)本地兩個列表中的信任值記錄有更新的時候就觸發(fā)上述的算法，進(jìn)行鏈接的更新．

節(jié)點鏈接關(guān)系的更新體現(xiàn)為網(wǎng)絡(luò)拓?fù)涞淖兓?jié)點通過更新同其他節(jié)點的鏈接關(guān)系，實現(xiàn)了同服務(wù)提供能力較強、信任度高的節(jié)點之間的連接關(guān)系．這樣，將會增大節(jié)點的資源搜索的內(nèi)容可達(dá)性，削減網(wǎng)絡(luò)中消息的流量，減少服務(wù)的搜索時間．

2.2 資源搜索機制

P2P系統(tǒng)中基于前一節(jié)網(wǎng)絡(luò)拓?fù)涞馁Y源搜索算法如下算法2：

1)首先請求節(jié)點q需要向其直接鄰居節(jié)點中信任度最大的節(jié)點發(fā)出資源搜索消息Q，其格式為{content，IPq，TTL}．其中TTL代表該消息的生存周期，content表示請求的資源，而IPq代表了請求者的地址．

2)如果節(jié)點q的信任度最大的直接鄰居節(jié)點r可以提供消息Q中所描述的資源，則向q返回一個應(yīng)答消息R，其格式為{answer，IPr}，其中answer代表應(yīng)答消息內(nèi)容，確實擁有q所需要的資源，IPr為r的地址，算法終止．

3)否則，當(dāng)節(jié)點r不能提供消息Q中所描述的資源并且TTL>0；則TTL=TTL-1，節(jié)點r將{content，IPq，TTL}再轉(zhuǎn)發(fā)給它自己的信任度最大的直接鄰居節(jié)點，如果TTL<0，則算法終止．

4)重復(fù)順序執(zhí)行算法中第2)步和第3)步．

5)當(dāng)q收到了應(yīng)答消息R，表明資源搜索成功，它將根據(jù)R來定位資源提供者的位置，并同資源提供者開始一次交易．

6)如果超過一定時間，還沒有q收到了應(yīng)答消息，則表明資源搜索失敗．

由于，本文的資源搜索機制是在基于信任鏈接的網(wǎng)絡(luò)拓?fù)渖线M(jìn)行的，因此，它能夠有效地抑制一些惡意節(jié)點的欺騙，具有良好的安全性能．

本文的搜索機制與文獻(xiàn)[3～4,7]是完全不同的，克服了它們現(xiàn)有的一些缺點．這些搜索機制的性能比較如表2 所示．

表2 幾種搜索機制的性能比較

3 仿真實驗

本節(jié)將通過系統(tǒng)模擬，通過和文獻(xiàn)[4]中的基于“gossip”的搜索機制進(jìn)行比較，來檢測該搜索機制的性能．作者在PC機上做了模擬實驗，其中CPU是Intel 酷睿2雙核 T5900，2G內(nèi)存；操作系統(tǒng)是Linux Ubuntu；網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)按照前面的定義通過Internet拓?fù)淠M工具BRITE產(chǎn)生的．

圖1 2種搜索機制的比較結(jié)果

在仿真實驗中，資源請求節(jié)點和資源目標(biāo)節(jié)點(服務(wù)節(jié)點)均是隨機分布的．每次交易完成后，節(jié)點將按照公式(2)更新服務(wù)節(jié)點的信任值，同時，按照3.1節(jié)中的算法1對請求節(jié)點的直接鄰居節(jié)點進(jìn)行更新，相應(yīng)地也改變了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)．資源請求節(jié)點分別使用文獻(xiàn)[4]中的搜索機制和本文的算法2進(jìn)行資源查找．在此，給出兩個定義．稱資源請求節(jié)點經(jīng)歷過的節(jié)點數(shù)除以網(wǎng)絡(luò)節(jié)點總數(shù)為搜索代價；稱查找成功的次數(shù)比所有資源請求總數(shù)為搜索成功率．顯然，一種有效的搜索機制應(yīng)該搜索代價小，搜索成功率高；或者這么說在要求達(dá)到相同的搜索成功率高情況下，效率高的搜索機制應(yīng)該搜索代價越小．在實驗中，每進(jìn)行了1 000次搜索請求后，作者就計算2種搜索機制下的平均搜索代價和搜索成功率．圖1給出兩種搜索機制的比較結(jié)果．

從圖1可以看出，在達(dá)到相同的搜索成功率高情況下，本文搜索機制的搜索代價較小，文獻(xiàn)[4]中的搜索機制較大．故本文搜索機制的效率要高．

4 小結(jié)

在研究了已有P2P網(wǎng)絡(luò)中資源搜索機制的若干局限性后，構(gòu)建了一種基于信任的拓?fù)浣Y(jié)構(gòu)和資源搜索機制．未來的研究工作包括如何在此基礎(chǔ)上建立完整的激勵機制，以提高P2P系統(tǒng)的公平性和動力，減少“free riding”行為等．

參考文獻(xiàn)：

[1] BO ZHU, SUSHIL JAJODIA, MOHAN S. Kankanhalli. Building trust in peer-to-peer systems: a review[J]. International Journal of Security and Networks, 2006, 1(1-2): 103-112.

[2] HUANG J C, LI X Q, WU J. A class-based search system in unstructured p2p networks[C]//Proceedings of the 21st International Conference on Advanced Information Networking and Applications, Niagara Falls, Canada, 2007,76-83.

[3] ION S, ROBERT M, DAVID L N,etal. Chord: A Scalable Peer-to-Peer Lookup Protocol for Internet Applications[J]. IEEE/ACM Transations on Networking, 2003, 11(1):17-32.

[4] STEPHEN B, ARPITA G, SALAJI P,etal. Gossip algorithms: design, analysis and applications[C]//Proceedings of IEEE Infocomm, Miami, 2005, 3:1 653-1 664.

[5] GNASA M, ALDA S, GRILGULL J,etal. Towards Virtual Knowledge Communities in Peer-to-Peer Networks[C]//Proceeding of ACM SIGIR Workshop on Distributed Information Retrieval, Canada: ACM Press, 2003:3-8.

[6] HERWIG U, MARKUS W. Cluster-building in P2P-community networks[J]. The Journal on Parallel and Distributed Computing and Systems, 2002, 12(5): 685-690.

[7] SRIPANIDKULCHAI K, MAGGS B, ZHANG H. Efficient Content Location Using Interest Based Locality in Peer-to-Peer Systems[C]//Proceeding of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, IEEE Press, 2003, 2 166-2 176.

[8] 竇 文,王懷民,賈 焰,等. 構(gòu)造基于推薦的Peer-to-Peer環(huán)境下的Trust 模型[J]. 軟件學(xué)報, 2004,15(4) :571-579.

[9] LIU H, ZHANG L M, ZENG B. An Anonymous Trustful-agents-based Trust Model for P2P Network[C]//Proceeding of 2009 Asia Pacific conference on Information processing, IEEE Press, 2009:426-429.