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

　　關(guān)鍵詞： P2P網(wǎng)絡(luò); 搜索; 訪問頻譜; 相似性

0 引言

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

1 相關(guān)工作

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

2 訪問譜線檢索模型

　　2.1 基本思想

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

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

　　2.2 模型建立

　　首先約定在理想網(wǎng)絡(luò)狀態(tài)下討論模型,，即任何節(jié)點都可以隨意地訪問到網(wǎng)絡(luò)中的其他節(jié)點。設(shè)P2P網(wǎng)絡(luò)節(jié)點集合為G={v1,v2,…,vn},。

　　定義1. 時段T（時長為L）內(nèi)節(jié)點vi訪問G中節(jié)點的次數(shù)稱為vi的交易活躍度,，即：

　　其中，分別為vi在時刻t和時刻t-L的訪問次數(shù),，μ為交易活躍閾值,。若A>M，則稱vi為交易活躍節(jié)點,，M為交易數(shù)閾值（一般為網(wǎng)絡(luò)節(jié)點單位時段平均訪問次數(shù)）,。

　　定義2. 時段T內(nèi)節(jié)點vi超過μ的訪問節(jié)點的數(shù)量稱為vi的交易覆蓋度，即：

　　若C>F,，則稱vi為交易廣泛節(jié)點,，F(xiàn)為交易覆蓋度閾值（一般為網(wǎng)絡(luò)節(jié)點單位時段平均交易覆蓋度）。

　　定義3. 時段T內(nèi)節(jié)點vi與vj訪問相同節(jié)點的差異量與訪問節(jié)點總數(shù)之比稱為vi與vj的訪問譜線相似度,，即：

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

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

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

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

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

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

　　2.3 檢索算法

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

　　輸入：源節(jié)點vs發(fā)出檢索請求M

　　輸出：檢索到目標節(jié)點vd或檢索失敗

　　(1) 接收M

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

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

　　(4) IF missing image file Then

　　由遠程連接節(jié)點轉(zhuǎn)發(fā)M和以隨機漫步方式向鄰節(jié)點轉(zhuǎn)發(fā)M

　　Else

　　以隨機漫步方式向鄰節(jié)點轉(zhuǎn)發(fā)M

　　(5) 繼續(xù)偵聽消息

3 仿真實驗

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

4 結(jié)論

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

　　參考文獻

　　[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.