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

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

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

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

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