摘 要： 針對在非結(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é)點信息對當(dāng)前或未來的行為和興趣的描述作用會隨時間而衰減，進而對行為預(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é)點訪問了相同的目標(biāo)節(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ā)，直到找到目標(biāo)節(jié)點。算法如下：

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

　　輸出：檢索到目標(biāo)節(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é)點的譜線滿足相似性標(biāo)準(zhǔn)。結(jié)果如圖1所示。不難發(fā)現(xiàn)節(jié)點的2、4、6、7、9頻段的訪問譜線相似度較高，表明它們在測試時段內(nèi)對相同節(jié)點進行了滿足譜線相似度的訪問。接著，挑選符合標(biāo)準(zhǔn)的訪問譜線相似節(jié)點建立遠程連接，并構(gòu)成不同覆蓋度的共有訪問譜線相似節(jié)點集，隨后再進行同規(guī)模的測試（查詢將借助遠程連接實現(xiàn)），統(tǒng)計平均查詢路徑長度的變化。結(jié)果如圖2所示?？梢钥闯龈采w度的擴大對訪問路徑的縮短有較大影響。

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.