摘  要： 非結(jié)構(gòu)化P2P網(wǎng)絡(luò)具有資源搜索效率不高，容易產(chǎn)生大量冗余信息等問(wèn)題，為此，提出了一種改進(jìn)的資源搜索策略。通過(guò)為網(wǎng)絡(luò)中的節(jié)點(diǎn)建立朋友節(jié)點(diǎn)來(lái)改進(jìn)傳統(tǒng)的非結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)資源搜索，并在此基礎(chǔ)上設(shè)計(jì)了一種新的資源搜索算法。仿真試驗(yàn)證明，該策略在一定程度上提高了非結(jié)構(gòu)化P2P資源搜索的效率，同時(shí)減少了網(wǎng)絡(luò)中的冗余信息量。
關(guān)鍵詞： 非結(jié)構(gòu)化P2P網(wǎng)絡(luò)；資源搜索；朋友節(jié)點(diǎn)；冗余信息

　效地組織和利用Internet上大量分布的計(jì)算、存儲(chǔ)以及信息等資源，充分釋放互聯(lián)網(wǎng)蘊(yùn)含的巨大的邊緣資源，以實(shí)現(xiàn)信息共享、即時(shí)通信、超級(jí)計(jì)算等目標(biāo)。P2P技術(shù)在當(dāng)今互聯(lián)網(wǎng)中有著廣泛的應(yīng)用，美國(guó)財(cái)富雜志更是將P2P技術(shù)列為未來(lái)影響IT技術(shù)的四大關(guān)鍵技術(shù)之一[1]。然而，計(jì)算機(jī)網(wǎng)絡(luò)是一個(gè)用戶分布廣泛、數(shù)量巨大，節(jié)點(diǎn)行為不可控、計(jì)算能力和網(wǎng)絡(luò)連接不均勻的復(fù)雜網(wǎng)絡(luò)，如何實(shí)現(xiàn)資源高效地搜索服務(wù)是P2P技術(shù)面臨的一個(gè)難題。
　本文針對(duì)現(xiàn)有非結(jié)構(gòu)化P2P網(wǎng)絡(luò)資源搜索效率不高，容易產(chǎn)生冗余信息等問(wèn)題，提出了一種改進(jìn)策略。通過(guò)增加節(jié)點(diǎn)的智能性來(lái)提高非結(jié)構(gòu)化P2P網(wǎng)絡(luò)資源的搜索效率，并采取一定的措施來(lái)減少網(wǎng)絡(luò)中冗余信息的產(chǎn)生。具體實(shí)現(xiàn)方法如下：在資源的搜索過(guò)程中，逐漸建立節(jié)點(diǎn)的朋友節(jié)點(diǎn)列表，相對(duì)于其他節(jié)點(diǎn)，朋友節(jié)點(diǎn)具有資源豐富及搜索成功率比較高等優(yōu)點(diǎn)；資源搜索請(qǐng)求首先在朋友節(jié)點(diǎn)上進(jìn)行，當(dāng)搜索失敗時(shí)，再采用最基本的搜索算法。
1 相關(guān)工作
　目前，P2P網(wǎng)絡(luò)按照拓?fù)浣Y(jié)構(gòu)可以分為結(jié)構(gòu)化P2P網(wǎng)絡(luò)和非結(jié)構(gòu)化P2P網(wǎng)絡(luò)。前者利用分布式Hash表（DHT），將節(jié)點(diǎn)組織成嚴(yán)格的拓?fù)浣Y(jié)構(gòu)，并將共享資源映射到特定的節(jié)點(diǎn)上，在資源搜索時(shí)采用相應(yīng)的定位方法，使得資源搜索能夠在確定的跳數(shù)內(nèi)完成，效率較高[2]。然而，P2P網(wǎng)絡(luò)的高動(dòng)態(tài)性使得結(jié)構(gòu)化P2P網(wǎng)絡(luò)的維護(hù)開(kāi)銷巨大；只支持關(guān)鍵字的精確查詢，不支持內(nèi)容、語(yǔ)義查詢；網(wǎng)絡(luò)節(jié)點(diǎn)的物理結(jié)構(gòu)被破壞，實(shí)際延遲大。
　非結(jié)構(gòu)化P2P網(wǎng)絡(luò)是以Gnutella為代表的一類網(wǎng)絡(luò)。這種網(wǎng)絡(luò)的結(jié)構(gòu)松散，共享資源的分布具有隨機(jī)性和不確定性，其主要采用中心搜索和泛洪（Flooding）搜索算法。中心搜索是指在網(wǎng)絡(luò)加入一個(gè)主要用于資源搜索的服務(wù)器，資源的搜索都在該服務(wù)器上完成，其容易產(chǎn)生服務(wù)瓶頸問(wèn)題，一旦服務(wù)器失效，整個(gè)網(wǎng)絡(luò)將崩潰；Flooding算法向所有鄰居節(jié)點(diǎn)廣播查詢信息，搜索根據(jù)預(yù)先設(shè)置的生命值TTL（Time to Live）來(lái)終止廣播查詢請(qǐng)求，其容易產(chǎn)生大量冗余信息，且搜索效率低。在以后的算法改進(jìn)中出現(xiàn)了Modified-BFS和Random Walk等算法。Modified-BFS算法雖然按照一定的概率隨機(jī)地選擇部分的節(jié)點(diǎn)發(fā)送消息，減少了網(wǎng)絡(luò)中的路由消息，降低了網(wǎng)絡(luò)的負(fù)載，但是資源搜索的成功率降低了；而Random Walk算法的最大劣勢(shì)在其表現(xiàn)的不穩(wěn)定性上，而且該算法的兩個(gè)參數(shù)（漫游消息的數(shù)量n以及漫游消息的步長(zhǎng)s）的恰當(dāng)取值也是個(gè)難點(diǎn)[3-4]。
　P2P網(wǎng)絡(luò)的可用性依賴于網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)貢獻(xiàn)資源，然而有參考文獻(xiàn)[5]顯示，在Gnutella中有70%的用戶節(jié)點(diǎn)從網(wǎng)絡(luò)中獲取資源，但它們對(duì)網(wǎng)絡(luò)的貢獻(xiàn)率卻幾乎為零，這種稱為“搭便車”的現(xiàn)象普遍存在于P2P網(wǎng)絡(luò)中，阻礙了網(wǎng)絡(luò)的高效運(yùn)行。因此，在非結(jié)構(gòu)化P2P網(wǎng)絡(luò)的資源搜索過(guò)程中，訪問(wèn)一些不存在共享資源或者共享資源很少的節(jié)點(diǎn)本身就是對(duì)網(wǎng)絡(luò)帶寬和節(jié)點(diǎn)計(jì)算能力的一種浪費(fèi)，完全可以通過(guò)一些策略將資源的搜索發(fā)生在那些搜索成功率比較高的節(jié)點(diǎn)上，這樣就大大提高了非結(jié)構(gòu)化P2P網(wǎng)絡(luò)資源搜索的效率。
　關(guān)于提高非結(jié)構(gòu)化P2P網(wǎng)絡(luò)資源搜索，參考文獻(xiàn)[6]提出了一種基于學(xué)習(xí)的搜索算法，其采用分布式的被動(dòng)學(xué)習(xí)方式，從歷史搜索結(jié)果中學(xué)習(xí)節(jié)點(diǎn)之間的興趣相似度，并指出保存歷史記錄可以對(duì)后面的節(jié)點(diǎn)發(fā)起的資源搜索產(chǎn)生借鑒意義。參考文獻(xiàn)[7]提出將網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分為超級(jí)節(jié)點(diǎn)和普通節(jié)點(diǎn)，資源搜索首先在超級(jí)節(jié)點(diǎn)上進(jìn)行，搜索失敗后再通過(guò)廣播搜索信息在普通節(jié)點(diǎn)上進(jìn)行。
2 改進(jìn)的資源搜索策略
2.1 朋友節(jié)點(diǎn)
　在本文中，朋友節(jié)點(diǎn)是指那些對(duì)以后的資源搜索具有重要意義的節(jié)點(diǎn)。和其他節(jié)點(diǎn)相比，朋友節(jié)點(diǎn)可能具有以下特點(diǎn)：（1）豐富的資源，很大程度上能滿足資源的搜索請(qǐng)求；（2）和搜索節(jié)點(diǎn)具有相同的興趣[6]。網(wǎng)絡(luò)中的任意節(jié)點(diǎn)可以選擇多個(gè)節(jié)點(diǎn)作為自己的朋友節(jié)點(diǎn)，并建立起自己的朋友節(jié)點(diǎn)列表。當(dāng)一個(gè)節(jié)點(diǎn)剛加入網(wǎng)絡(luò)時(shí)，其朋友節(jié)點(diǎn)列表長(zhǎng)度為零，在以后的資源搜索過(guò)程中，朋友節(jié)點(diǎn)列表逐漸建立起來(lái)。朋友節(jié)點(diǎn)列表長(zhǎng)度不能無(wú)限大，否則就失去了意義。朋友節(jié)點(diǎn)列表需要不斷地更新和維護(hù)，以便增加新的更有意義的節(jié)點(diǎn)和淘汰那些舊的逐漸失去意義的節(jié)點(diǎn)。
2.2 朋友節(jié)點(diǎn)列表
　本文將朋友節(jié)點(diǎn)列表設(shè)計(jì)成一個(gè)線性鏈表，該線性鏈表除了有一個(gè)指示其入口地址的指針*L外，還需要增加size和Maxsize兩個(gè)變量。其中，size指示現(xiàn)有的朋友節(jié)點(diǎn)列表的長(zhǎng)度；Maxsize指示該線性鏈表不能超過(guò)的最大長(zhǎng)度。因此，網(wǎng)絡(luò)中某一節(jié)點(diǎn)的朋友節(jié)點(diǎn)列表定義為：FriendNode_List（*L，size，Maxsize）。
當(dāng)網(wǎng)路中某一節(jié)點(diǎn)在某一時(shí)刻發(fā)起資源搜索請(qǐng)求并成功后，就將包含該目標(biāo)資源的節(jié)點(diǎn)視為自己的朋友節(jié)點(diǎn)，并將其加入到自己的朋友節(jié)點(diǎn)列表中。很顯然，在朋友節(jié)點(diǎn)列表中只需要記錄該目標(biāo)節(jié)點(diǎn)的地址即可，即IP_Address。另外，由于朋友節(jié)點(diǎn)列表需要不斷地更新和維護(hù)，因此需要引入一個(gè)變量來(lái)衡量朋友節(jié)點(diǎn)的意義程度，很顯然，在某一節(jié)點(diǎn)上獲取資源的次數(shù)越多，該節(jié)點(diǎn)就越有意義。因此，引入一個(gè)變量num指示成功獲取資源的次數(shù)；再增加一個(gè)變量Extra表示一些額外的附加信息，例如Extra可以記錄最后一次成功獲取資源的時(shí)間。因此，朋友節(jié)點(diǎn)定義為FriendNode（*next，IP_Address，num，Extra）。朋友節(jié)點(diǎn)列表的組織結(jié)構(gòu)如圖1所示。

　圖1中，為了取參數(shù)方便，將變量size的值存放在了頭節(jié)點(diǎn)的num值域中。下面給出了定義朋友節(jié)點(diǎn)和初始化線性鏈表（由于文章篇幅限制，只給出部分實(shí)現(xiàn)代碼）。
//定義朋友節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)
#define Maxsize 50//定義朋友節(jié)點(diǎn)列表的最大長(zhǎng)度為50
typedef struct FriendNode{
struct FriendNode *next；
DataType IP_Address；
int num；
DataType Extra；
}FriendNode，*Lnode；
//初始化朋友節(jié)點(diǎn)列表，
//返回指向第一個(gè)節(jié)點(diǎn)（頭結(jié)點(diǎn)）的指針
Lnode*FriendNode_List（）{
L=（Lnode*）malloc（sizeof（Lnode））；
//開(kāi)辟一個(gè)存儲(chǔ)朋友節(jié)點(diǎn)信息的空間
L->next=null；//將next域置為空
L->num=0；//朋友節(jié)點(diǎn)列表的初始長(zhǎng)度為0
return L；}
2.3 朋友節(jié)點(diǎn)列表的維護(hù)
　此時(shí)，網(wǎng)絡(luò)中任意一個(gè)節(jié)點(diǎn)A維護(hù)自己的朋友節(jié)點(diǎn)列表FriendNode_List（*L，size，Maxsize）的算法如下（文字描述）：
?。?）節(jié)點(diǎn)A在某一節(jié)點(diǎn)B成功獲取了資源，則節(jié)點(diǎn)A根據(jù)節(jié)點(diǎn)B的IP地址判斷其是否已經(jīng)存在自己的朋友節(jié)點(diǎn)列表上，如果是，轉(zhuǎn)向（2），否則轉(zhuǎn)向（3）；
?。?）修改節(jié)點(diǎn)B的num值，置num+=1，結(jié)束；
　（3）判斷size的值是否小于Maxsize，如果是，則轉(zhuǎn)向（4），否則轉(zhuǎn)向（5）；
?。?）增加一個(gè)朋友節(jié)點(diǎn)域，將其中的IP_Address的值設(shè)為節(jié)點(diǎn)B的IP地址，num的值設(shè)為1，朋友節(jié)點(diǎn)列表長(zhǎng)度size+=1，結(jié)束；
　（5）找出表中num值最小的元素，將B的IP地址取代原來(lái)節(jié)點(diǎn)的IP_Address值，同時(shí)將num的值置為1，結(jié)束。
　參考操作系統(tǒng)中的缺頁(yè)中斷算法，當(dāng)朋友節(jié)點(diǎn)列表長(zhǎng)度已經(jīng)達(dá)到最大后，也可以將那些最近最久沒(méi)有獲得過(guò)資源的朋友節(jié)點(diǎn)刪除。
2.4 改進(jìn)的資源搜索算法
　非結(jié)構(gòu)化P2P網(wǎng)絡(luò)資源搜索實(shí)質(zhì)上就是將包含目標(biāo)資源的搜索信息發(fā)送到網(wǎng)絡(luò)中其他節(jié)點(diǎn)中去，如果某一節(jié)點(diǎn)中存在目標(biāo)資源，則兩節(jié)點(diǎn)建立網(wǎng)絡(luò)連接完成該資源的傳輸?，F(xiàn)在，網(wǎng)絡(luò)中的節(jié)點(diǎn)維護(hù)著一張朋友節(jié)點(diǎn)列表，相對(duì)于其他節(jié)點(diǎn)，朋友節(jié)點(diǎn)具有資源豐富、資源搜索成功率高的優(yōu)點(diǎn)，因此本文中改進(jìn)的資源搜索算法敘述如下：
?。?）在某一時(shí)刻，節(jié)點(diǎn)A發(fā)起資源搜索請(qǐng)求，設(shè)置TTL的值為2，將資源搜索信息按照自己的朋友節(jié)點(diǎn)列表發(fā)送到每一個(gè)朋友節(jié)點(diǎn)上。
?。?）TTL的值減1，假設(shè)節(jié)點(diǎn)B是A的朋友節(jié)點(diǎn)，如果節(jié)點(diǎn)B滿足該資源搜索請(qǐng)求，則兩節(jié)點(diǎn)建立連接完成該資源的傳輸同時(shí)修改自己的朋友節(jié)點(diǎn)列表，結(jié)束；否則轉(zhuǎn)向（3）。
?。?）節(jié)點(diǎn)B將該資源搜索信息根據(jù)自己的朋友節(jié)點(diǎn)列表轉(zhuǎn)發(fā)到所有的朋友節(jié)點(diǎn)中去，重復(fù)過(guò)程（2），資源搜索信息隨著TTL的值為0時(shí)終止傳輸。
?。?）如果上述資源搜索失敗，則采用Flooding搜索算法。
也許上述改進(jìn)的資源搜索算法不適用于網(wǎng)絡(luò)中剛加入的節(jié)點(diǎn)，因?yàn)槠溥€沒(méi)有發(fā)起資源搜索請(qǐng)求，所以其朋友節(jié)點(diǎn)列表的長(zhǎng)度為0。這個(gè)問(wèn)題可以很容易解決，例如當(dāng)一個(gè)節(jié)點(diǎn)剛加入網(wǎng)絡(luò)時(shí)，直接復(fù)制其鄰居節(jié)點(diǎn)的朋友節(jié)點(diǎn)列表。
3 性能評(píng)估
　本文的意義是通過(guò)建立朋友節(jié)點(diǎn)列表盡量將資源搜索發(fā)生在一些搜索成功率比較高的節(jié)點(diǎn)上，這樣就盡量避免了Flooding算法的使用，提高資源搜索效率。同時(shí)，采用基于朋友節(jié)點(diǎn)列表的資源搜索時(shí)，將TTL的值設(shè)為2是為了一方面擴(kuò)大有意義的節(jié)點(diǎn)的搜索范圍，另一方面避免冗余信息的產(chǎn)生，如圖2所示。

　圖2中顯示了節(jié)點(diǎn)A、B、E的朋友節(jié)點(diǎn)?？梢钥闯觯?jié)點(diǎn)A和節(jié)點(diǎn)B有一個(gè)相同的朋友節(jié)點(diǎn)D；節(jié)點(diǎn)A和節(jié)點(diǎn)E有一個(gè)共同的朋友節(jié)點(diǎn)C；節(jié)點(diǎn)B和E有一個(gè)共同的朋友節(jié)點(diǎn)D。當(dāng)節(jié)點(diǎn)A發(fā)起資源搜索時(shí)，會(huì)把搜索信息發(fā)給節(jié)點(diǎn)B、C、D。如果節(jié)點(diǎn)B上不存在節(jié)點(diǎn)A想要的資源，由于TTL的值設(shè)為2，所以節(jié)點(diǎn)B將繼續(xù)轉(zhuǎn)發(fā)搜索信息到節(jié)點(diǎn)D、E、F，可以看出節(jié)點(diǎn)D接受資源搜索信息兩次，這就引起了無(wú)效的資源搜索信息轉(zhuǎn)發(fā)。如果將TTL的值設(shè)為3或者更高，那么如果當(dāng)節(jié)點(diǎn)E不滿足節(jié)點(diǎn)A的資源請(qǐng)求時(shí)會(huì)繼續(xù)將搜索信息發(fā)送給節(jié)點(diǎn)C和D，很顯然，由節(jié)點(diǎn)E轉(zhuǎn)發(fā)的兩次資源搜索信息都是無(wú)效的，這就引起了網(wǎng)絡(luò)帶寬資源的浪費(fèi)，這也是Flooding算法的根本缺陷所在。筆者在以前參考的論文中，有的論文提出根據(jù)節(jié)點(diǎn)共享文檔的相似性建立相同興趣節(jié)點(diǎn)，將資源搜索信息首先轉(zhuǎn)發(fā)到具有相同興趣的節(jié)點(diǎn)上，如果該節(jié)點(diǎn)不滿足資源搜索，則繼續(xù)轉(zhuǎn)發(fā)到自己的相同興趣節(jié)點(diǎn)上，可以看出，這種說(shuō)法是不準(zhǔn)確的，在此給出糾正。
　從上面的說(shuō)明中可以看出，當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)逐漸建立起自己的朋友節(jié)點(diǎn)列表后，下次搜索資源時(shí)，通過(guò)將資源的搜索信息發(fā)送到朋友節(jié)點(diǎn)以及朋友的朋友節(jié)點(diǎn)（即兩級(jí)搜索），就基本上可以做到搜索覆蓋了網(wǎng)絡(luò)中的大部分有意義的節(jié)點(diǎn)。也就是說(shuō)，當(dāng)一個(gè)節(jié)點(diǎn)成功建立起自己的朋友節(jié)點(diǎn)列表后，后來(lái)的資源搜索基本上就可以在一跳或者兩跳內(nèi)完成。
4 實(shí)驗(yàn)驗(yàn)證
　本次模擬實(shí)驗(yàn)在一臺(tái)PC上完成，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)由FLOD算法產(chǎn)生，構(gòu)造了一個(gè)具有1 000個(gè)節(jié)點(diǎn)和10 000份文檔的P2P網(wǎng)絡(luò)，文檔在節(jié)點(diǎn)間采用80：20分布（即網(wǎng)絡(luò)中20%的節(jié)點(diǎn)擁有全網(wǎng)80%的文檔，剩下80%的節(jié)點(diǎn)只擁有剩下的20%的文檔）。
　本次試驗(yàn)通過(guò)設(shè)置朋友節(jié)點(diǎn)列表長(zhǎng)度與全網(wǎng)所有節(jié)點(diǎn)數(shù)目的比例P，來(lái)觀察資源搜索在一跳或兩跳內(nèi)的搜索成功率S（即資源搜索通過(guò)轉(zhuǎn)發(fā)朋友節(jié)點(diǎn)列表）。理論上，朋友節(jié)點(diǎn)列表長(zhǎng)度最大取值為（n為網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)目）。
　搜索結(jié)果如圖3所示。其中，P的取值分別為0.005、0.01、0.015、0.02、0.025、0.03、0.035、0.04、0.045，即朋友節(jié)點(diǎn)長(zhǎng)度分別為5、10，、15、20、25、30、35、40、45時(shí)的搜索成功率S。

　從圖3可以看出，S的值隨著P的值增大而明顯增大，當(dāng)朋友節(jié)點(diǎn)列表長(zhǎng)度接近或略大于40時(shí)，S的值接近于1，這也就驗(yàn)證了預(yù)期的設(shè)想。
　在網(wǎng)絡(luò)信息流量方面，由于朋友節(jié)點(diǎn)列表的存在，資源搜索信息的轉(zhuǎn)發(fā)是明確的，即資源搜索信息不會(huì)轉(zhuǎn)發(fā)到一個(gè)先前不確定的節(jié)點(diǎn)上，這也就解決了Flooding算法產(chǎn)生大量冗余信息的根本問(wèn)題所在。
本文通過(guò)為網(wǎng)絡(luò)中的節(jié)點(diǎn)建立朋友節(jié)點(diǎn)列表，將資源的搜索發(fā)生在資源搜索成功率比較高的節(jié)點(diǎn)上，這樣既提高了資源的搜索效率，又避免了大量冗余信息的產(chǎn)生。試驗(yàn)證明該策略簡(jiǎn)單可行，當(dāng)一個(gè)節(jié)點(diǎn)在發(fā)起多次資源搜索請(qǐng)求并成功建立起自己的朋友節(jié)點(diǎn)列表后，以后的資源搜索通過(guò)轉(zhuǎn)發(fā)朋友節(jié)點(diǎn)列表就基本上能在一跳或兩跳內(nèi)完成，這樣也驗(yàn)證了預(yù)期的設(shè)想。
參考文獻(xiàn)
[1] GONG L. Peer-to-peer networks in action[J]. IEEE Internet Computing， 2002，6（1）：37-39.
[2] 王麗莉，孫波，肖永康，等.結(jié)構(gòu)化P2P資源搜索算法研究綜述[J].計(jì)算機(jī)應(yīng)用研究，2009，26（10）：3621-3624.
[3] 張文，趙子銘，楊天路，等.P2P網(wǎng)絡(luò)技術(shù)原理與C++開(kāi)發(fā)案例[M].北京：人民郵電出版社，2008.
[4] 張偉，歐陽(yáng)松.一種基于非結(jié)構(gòu)化對(duì)等網(wǎng)絡(luò)的改進(jìn)搜索算法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2009，21（1）：59-61.
[5] ADAR E， HUBERMAN B A. Free-riding on Gnutella[J]. First Monday， 2000，5（10）：1-22.
[6] 陳海濤，龔正虎，黃遵國(guó).一種基于學(xué)習(xí)的P2P搜索算法[J].計(jì)算機(jī)研究與發(fā)展，2005，42（9）：1600-1604.
[7] 曾曉云.基于Chord協(xié)議的混合P2P模型[J].計(jì)算機(jī)工程，2010，36（7）：112-115.