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

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

0 引言

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

1 相關(guān)工作

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

2 訪問(wèn)譜線檢索模型

　　2.1 基本思想

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

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

　　2.2 模型建立

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

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

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

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

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

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

　　其中，分別為 vi與vj在時(shí)刻t的請(qǐng)求訪問(wèn)次數(shù)，

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

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

　　定理1. 節(jié)點(diǎn)的訪問(wèn)路徑長(zhǎng)度與節(jié)點(diǎn)在G中所占的比例成反比。

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

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

　　2.3 檢索算法

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

　　輸入：源節(jié)點(diǎn)vs發(fā)出檢索請(qǐng)求M

　　輸出：檢索到目標(biāo)節(jié)點(diǎn)vd或檢索失敗

　　(1) 接收M

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

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

　　(4) IF missing image file Then

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

　　Else

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

　　(5) 繼續(xù)偵聽(tīng)消息

3 仿真實(shí)驗(yàn)

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

4 結(jié)論

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

　　參考文獻(xiàn)

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