摘 要： 針對在非結構化對等網絡(Unstructured Peer to Peer)中查找資源時傳統資源搜索方法的檢索效率不高、通信開銷過大的問題，提出了一種新的基于訪問興趣相似性P2P網絡模型。在對網絡結構不作全面改變的情況下，通過發現訪問頻譜相似節點，建立少量訪問頻譜相似節點間的遠程連接，可以改善傳統的非結構化對等網絡資源搜索，并在此基礎上設計了一種資源搜索算法。仿真試驗證明，該模型在一定程度上提高了非結構化P2P資源搜索的效率，同時減少了網絡中的通信冗余信息量。

　　關鍵詞： P2P網絡; 搜索; 訪問頻譜; 相似性

0 引言

　　以小世界理論構建的無結構P2P網絡融合了規則網和隨機網的特點，可以明顯改善網絡的查詢性能[1-3]。其實它所反映的特性從生活中就能觀察到，兩個從未有過交往的家庭會因一對兒女的聯姻而逐漸熟悉,最終所有家庭成員的交往都會變得更直接和密切。在P2P網絡中也一樣，只要增加少量節點間的遠程連接，不用全面改變網絡原有的結構就可以有效地縮短節點間相互訪問路徑的長度,進而改善整個網絡的綜合效能。但參考文獻[4-5]的研究表明，遠程連接節點的選擇是有條件的，隨意建立起的連接并不能達到預想的效果。仿真實驗也證實了這點。

1 相關工作

　　參考文獻[6]采用隨機均勻分布策略建立節點的遠程連接，并證明檢索路徑長度可以縮短并低于O(log2n)。參考文獻[4]根據網絡節點的流行度服從Zipf分布的特性提出了新方法，得到比參考文獻[6]更好的檢索結果。它們采用的方法是借助節點的本地信息去選擇要建立遠程連接的節點，使算法簡單且開銷比較小，但只利用了節點的靜態信息。舊的節點信息對當前或未來的行為和興趣的描述作用會隨時間而衰減，進而對行為預測會產生較大的偏差[7-9]。另一方面，參考文獻[6-8]的研究表明，網絡節點產生的訪問興趣和行為通常存在一個穩定期，即使訪問興趣開始改變,發生突變的可能性也比較小。正是人們興趣的持續性促成了網絡上交易圈的形成并產生交織，從而引發網絡的小世界現象。并且交際圈的范圍和交織部分的大小對小世界效應的影響很大。因此，本文提出基于訪問興趣相似性P2P網絡模型，通過節點行為特征（簡稱訪問譜線）的比較，發現節點訪問譜線的相似性，從而選出具有訪問譜線穩定性高且興趣覆蓋寬的節點作為遠程連接節點，進而達到縮短查找路徑的效果。

2 訪問譜線檢索模型

　　2.1 基本思想

　　訪問譜線相似的原因是節點訪問了相同的目標節點集合。但現實網絡中節點的訪問譜線存在較大差異，因為節點包涵的信息不均衡，被重復訪問的幾率也不同。仿真實驗對網絡節點形成的訪問譜線及其相似性進行了比對，結果表明，在規定時間段內節點對網絡資源的訪問形成了非常相似的訪問譜線片段。另一個實驗則表明，將有相似興趣的節點連接起來，可以使它們以及與它們有相似興趣的節點的平均查詢路徑長度大為縮短。如果節點興趣面較廣，則可以大范圍影響節點的性能。

　　利用以上特性，模型的設計原則是建立遠程連接時應選擇交易活躍、興趣廣泛、訪問譜線相似的節點。

　　2.2 模型建立

　　首先約定在理想網絡狀態下討論模型，即任何節點都可以隨意地訪問到網絡中的其他節點。設P2P網絡節點集合為G={v1,v2,…,vn}。

　　定義1. 時段T（時長為L）內節點vi訪問G中節點的次數稱為vi的交易活躍度，即：

　　其中，分別為vi在時刻t和時刻t-L的訪問次數，μ為交易活躍閾值。若A>M，則稱vi為交易活躍節點，M為交易數閾值（一般為網絡節點單位時段平均訪問次數）。

　　定義2. 時段T內節點vi超過μ的訪問節點的數量稱為vi的交易覆蓋度，即：

　　若C>F，則稱vi為交易廣泛節點，F為交易覆蓋度閾值（一般為網絡節點單位時段平均交易覆蓋度）。

　　定義3. 時段T內節點vi與vj訪問相同節點的差異量與訪問節點總數之比稱為vi與vj的訪問譜線相似度，即：

　　其中，分別為 vi與vj在時刻t的請求訪問次數，

　　若Sij>S，則稱vi與vj為訪問譜線相似節點，記為，S為訪問譜線相似度閾值。

　　定義4. 若，則稱為G的共有訪問譜線相似節點集。

　　定理1. 節點的訪問路徑長度與節點在G中所占的比例成反比。

　　證明：假設為建立一個長度為的索引表，記錄節點的IP地址，借助索引表a對其他節點的訪問路徑長度不會超過，如果所有節點索引表的內容不重復且都是訪問譜線相似節點，那么節點的訪問路徑長度不會超過。所以節點的訪問路徑長度與節點在G中所占的比例成反比，即節點越多，節點的訪問路徑長度越短。

　　因此，建立模型的目的就是產生盡量多的訪問譜線相似節點，并且形成共有訪問譜線相似節點集。

　　2.3 檢索算法

　　檢索時消息M的傳播方式是：一般節點以隨機漫步方式轉發給鄰居節點，遇到有遠程連接的節點，則利用遠程連接和鄰居節點一起轉發，直到找到目標節點。算法如下：

　　輸入：源節點vs發出檢索請求M

　　輸出：檢索到目標節點vd或檢索失敗

　　(1) 接收M

　　(2) 查詢本節點ν有沒有所要找的資源，有則向vd返回結果，轉步驟 (5)

　　(3) IF TTL=0 Then Goto (5)

　　(4) IF missing image file Then

　　由遠程連接節點轉發M和以隨機漫步方式向鄰節點轉發M

　　Else

　　以隨機漫步方式向鄰節點轉發M

　　(5) 繼續偵聽消息

3 仿真實驗

　　仿真實驗的目的是驗證模型縮短檢索路徑長度的有效性。對網絡節點形成的訪問譜線進行相似性分析，選擇符合模型要求的節點建立遠程連接進行檢索測試，分析節點檢索路徑長度的變化。測試網絡設置1 000個網絡節點，在10 min內每個節點以每秒隨機產生1個對其他網絡節點的訪問，并統計它們的平均查詢路徑長度。隨機抽取20個節點，分析所形成的訪問譜線及其相似性，發現有3個節點的譜線滿足相似性標準。結果如圖1所示。不難發現節點的2、4、6、7、9頻段的訪問譜線相似度較高，表明它們在測試時段內對相同節點進行了滿足譜線相似度的訪問。接著，挑選符合標準的訪問譜線相似節點建立遠程連接，并構成不同覆蓋度的共有訪問譜線相似節點集，隨后再進行同規模的測試（查詢將借助遠程連接實現），統計平均查詢路徑長度的變化。結果如圖2所示。可以看出覆蓋度的擴大對訪問路徑的縮短有較大影響。

4 結論

　　本文根據網絡的小世界特性，提出用新方法對節點在資源查找過程中形成的訪問頻譜進行相似性對比分析，通過發現網絡中具有訪問頻譜相似的節點，再從中篩選出交易活動能力強、交易范圍廣的節點，利用它們形成的超出一般節點的交易集合及其交集建立節點間的遠程連接。仿真實驗對模型的有效性給予了驗證，實驗結果表明，新方法使網絡通信范圍和訪問路徑長度大幅度縮短，改善了網絡的資源檢索效能，減少了網絡帶寬資源的消耗。

　　參考文獻

　　[1] Newman M E J, Barabasi A L,Watts D J. The structure and dynamics of networks[M]．Princeton，New Jersey：Princeton University Press，2006．

　　[2] Hui K Y K，Lui J C S，Yau D K Y．Small-world overlay P2P networks：construction，management and handling of dynamic flash crowds[J]．Computer Networks，2006，50(15)：2727-2746．

　　[3] Zhang Yuxiang, Zhang Hongke. A load balancing method in superlayer of hierarchical DHT-based P2P network[J]. Chinese Journal of Computers, 2010, 33(9):1580-1590.

　　[4] Shen Jingbo, Li Jinlong，Wang Xufa. Efect of long-distance connections selection method on object lookup in P2P network[J]. Journal of Chinese Computer Systems, 2011, 32(1):99-102.

　　[5] Li Zhen, Duan Hancong, Nie Xiaowen, et al. Routing optimization on the layered peer-to-peer management network[J]. Journal of Chinese Computer Systems, 2012, 31(1):54-57.

　　[6] Kleinberg J．The small—world phenomenon：an algorithm perspective[C]. Proceedings of 32nd Annual ACM Symposium on Theory of Computing，2000:163-170.

　　[7] Huang Yongsheng, Meng Xiangwu, Zhang Yujie. Strategy of content location of P2P based on the social network[J]. Journal of Software, 2010,21(10):2622-2630.

　　[8] Zheng Xiaojian, Zheng Xiaolan, Li Tong, et al. High frequency access areas discovery algorithm in peer-to-peer network[J]. Computer Engineering and Design, 2014,35(3):780-784.

　　[9] Li Pu, Chen Shiping, Li Jianfeng. Cloud resources locating algorithm based on peer-to-peer network[J]. Application Research of Computers, 2013, 30(2):570-573.