魏長(zhǎng)明

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

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

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

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

1 信任計(jì)算

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

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

表1 評(píng)價(jià)說明

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

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

TS=σTSC+E(s,i)

(1)

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

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

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

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

(2)

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

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

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

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

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

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

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

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

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

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

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

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

定義3記Tj為i對(duì)j的信任值．

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

隨著關(guān)于特定目標(biāo)節(jié)點(diǎn)的交互經(jīng)驗(yàn)的積累，以及目標(biāo)節(jié)點(diǎn)行為的變化等因素，都將導(dǎo)致對(duì)目標(biāo)節(jié)點(diǎn)信任判斷的更新，相應(yīng)的，也需要更新鏈接以反映信任因素的變化．這里給出了一個(gè)基于信任鏈接更新算法，使網(wǎng)絡(luò)中的節(jié)點(diǎn)同具有更強(qiáng)的服務(wù)能力的節(jié)點(diǎn)建立更為緊密的交互關(guān)系．在i與目標(biāo)節(jié)點(diǎn)j交易完成，通過公式(2)計(jì)算獲得節(jié)點(diǎn)j的信任值Tj后，若j∈Mi-Ni，Ni中h的信任值最小，且Tj>Th，則用j的鏈接替換同h的鏈接；若j∈Ni，Mi-Ni中h的信任值最大，且Th>Tj，則用h的鏈接替換同j的鏈接．節(jié)點(diǎn)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)本地兩個(gè)列表中的信任值記錄有更新的時(shí)候就觸發(fā)上述的算法，進(jìn)行鏈接的更新．

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

2.2 資源搜索機(jī)制

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

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

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

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

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

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

6)如果超過一定時(shí)間，還沒有q收到了應(yīng)答消息，則表明資源搜索失?。?/p>

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

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

表2 幾種搜索機(jī)制的性能比較

3 仿真實(shí)驗(yàn)

本節(jié)將通過系統(tǒng)模擬，通過和文獻(xiàn)[4]中的基于“gossip”的搜索機(jī)制進(jìn)行比較，來檢測(cè)該搜索機(jī)制的性能．作者在PC機(jī)上做了模擬實(shí)驗(yàn)，其中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種搜索機(jī)制的比較結(jié)果

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

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

4 小結(jié)

在研究了已有P2P網(wǎng)絡(luò)中資源搜索機(jī)制的若干局限性后，構(gòu)建了一種基于信任的拓?fù)浣Y(jié)構(gòu)和資源搜索機(jī)制．未來的研究工作包括如何在此基礎(chǔ)上建立完整的激勵(lì)機(jī)制，以提高P2P系統(tǒng)的公平性和動(dò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é)報(bào), 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.