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

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

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

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

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