一種無(wú)結(jié)構(gòu)對(duì)等網(wǎng)絡(luò)資源發(fā)現(xiàn)方法

薛冰冰，俞衛(wèi)華，霍 華

(河南科技大學(xué)電子信息工程學(xué)院，河南洛陽(yáng)471023)

0 引言

對(duì)等網(wǎng)絡(luò)主要采用非集中式的拓?fù)浣Y(jié)構(gòu)，各節(jié)點(diǎn)之間直接共享資源，信息傳播迅速，網(wǎng)絡(luò)中用戶間信息共享的前提是資源的定位。因此，覆蓋網(wǎng)絡(luò)中的資源發(fā)現(xiàn)機(jī)制是P2P技術(shù)研究的重點(diǎn)。

按照資源發(fā)現(xiàn)機(jī)制，對(duì)等覆蓋網(wǎng)絡(luò)大致可分為混合式、結(jié)構(gòu)化和無(wú)結(jié)構(gòu)P2P網(wǎng)絡(luò)[1］?；旌鲜骄W(wǎng)絡(luò)體系仍沒(méi)有擺脫中心化的特點(diǎn)，存在網(wǎng)絡(luò)瓶頸和單點(diǎn)故障等局限性，Napster是典型的代表。結(jié)構(gòu)化P2P主要采用基于DHT[2］的分布式發(fā)現(xiàn)策略，這種發(fā)現(xiàn)機(jī)制對(duì)特定資源的發(fā)現(xiàn)效率較高，適合規(guī)模較小的網(wǎng)絡(luò)應(yīng)用。分布式無(wú)結(jié)構(gòu)P2P網(wǎng)絡(luò)，如Gnutella[3］，在拓?fù)浣Y(jié)構(gòu)上沒(méi)有明確控制，節(jié)點(diǎn)的動(dòng)態(tài)變化不會(huì)對(duì)網(wǎng)絡(luò)結(jié)構(gòu)造成影響，適合較大規(guī)模的P2P應(yīng)用，但如何使節(jié)點(diǎn)物理位置與上層覆蓋網(wǎng)絡(luò)相一致[4］，提高搜索成功率[5］，降低路由延遲[6-7］等問(wèn)題也成為關(guān)注熱點(diǎn)。

分布式無(wú)結(jié)構(gòu)對(duì)等網(wǎng)絡(luò)中，節(jié)點(diǎn)和資源都是隨機(jī)分布的，資源請(qǐng)求者只能通過(guò)鄰居節(jié)點(diǎn)將消息轉(zhuǎn)發(fā)擴(kuò)散。目前，常見(jiàn)的無(wú)結(jié)構(gòu)P2P資源發(fā)現(xiàn)方法有Flooding[8］、Random Walks[9］等。這些方法采用盲目的消息轉(zhuǎn)發(fā)機(jī)制，可以快速定位資源，有較好的容錯(cuò)能力，但隨著網(wǎng)絡(luò)規(guī)模的增大，節(jié)點(diǎn)有可能多次收到相同的資源請(qǐng)求，會(huì)產(chǎn)生大量查詢數(shù)據(jù)。

采用Flooding的搜索方法，節(jié)點(diǎn)請(qǐng)求資源時(shí)，首先將請(qǐng)求發(fā)送給鄰居節(jié)點(diǎn)，若鄰居節(jié)點(diǎn)中存在擁有資源的節(jié)點(diǎn)，則響應(yīng)源節(jié)點(diǎn);否則，所有鄰居節(jié)點(diǎn)將向其各自的鄰居節(jié)點(diǎn)繼續(xù)轉(zhuǎn)發(fā)請(qǐng)求消息，直到發(fā)現(xiàn)目標(biāo)或者消息跳步達(dá)到了設(shè)置的最大范圍。

Random Walk發(fā)現(xiàn)的方法中，節(jié)點(diǎn)不再將請(qǐng)求消息轉(zhuǎn)發(fā)至所有鄰居，而是隨機(jī)選擇k個(gè)鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)消息，這種方法產(chǎn)生的消息流量少，但增加了網(wǎng)絡(luò)搜索時(shí)延。針對(duì)無(wú)結(jié)構(gòu)對(duì)等網(wǎng)絡(luò)資源發(fā)現(xiàn)中出現(xiàn)的問(wèn)題，k-Random-Walker[10］、Modified-BFS等改進(jìn)的搜索算法相繼提出，本文在研究相關(guān)優(yōu)化策略的基礎(chǔ)上，提出了一種基于興趣相似機(jī)制的資源發(fā)現(xiàn)方法，將興趣相似的節(jié)點(diǎn)組成域，根據(jù)節(jié)點(diǎn)的興趣相似度動(dòng)態(tài)改變域內(nèi)的節(jié)點(diǎn)構(gòu)成，同時(shí)，通過(guò)域之間的友好度來(lái)提高路由效率。

1 興趣相似機(jī)制

首先定義了相關(guān)網(wǎng)絡(luò)模型和節(jié)點(diǎn)間興趣相似度，并在此基礎(chǔ)上給出基于節(jié)點(diǎn)興趣相似度的資源發(fā)現(xiàn)方法DPIS。節(jié)點(diǎn)在信息傳遞過(guò)程中，維護(hù)相應(yīng)的興趣度索引，依據(jù)各自的興趣度索引動(dòng)態(tài)調(diào)整域內(nèi)成員;域內(nèi)資源發(fā)現(xiàn)失效的情況下，通過(guò)域友好度索引導(dǎo)向路由，減少消息轉(zhuǎn)發(fā)過(guò)程中的冗余。

1.1 覆蓋網(wǎng)模型

無(wú)結(jié)構(gòu)對(duì)等系統(tǒng)對(duì)覆蓋網(wǎng)拓?fù)錄](méi)有嚴(yán)格限制，考慮與物理網(wǎng)絡(luò)的匹配，首先將物理相近的節(jié)點(diǎn)分組，再根據(jù)節(jié)點(diǎn)間的興趣相似度，將系統(tǒng)中興趣相似度接近的節(jié)點(diǎn)劃分在同一域中，形成重疊網(wǎng)絡(luò)。組內(nèi)和域內(nèi)均選擇性能優(yōu)越的節(jié)點(diǎn)作為超節(jié)點(diǎn)，其中，保存本組或本域內(nèi)普通節(jié)點(diǎn)的數(shù)量、資源等相關(guān)信息，并維護(hù)域友好度索引表，記錄頻繁與之聯(lián)系的域排序。域內(nèi)普通節(jié)點(diǎn)中除保存自身資源信息，還需要維護(hù)興趣相似度索引，記錄與之興趣相似度最相近的若干節(jié)點(diǎn)信息。組和域的劃分如圖1所示。資源發(fā)現(xiàn)首先在本域內(nèi)的同組節(jié)點(diǎn)中進(jìn)行，若同組域內(nèi)發(fā)現(xiàn)失效，則在域內(nèi)其他組的節(jié)點(diǎn)中進(jìn)行，最后考慮跨域搜索。

節(jié)點(diǎn)間的興趣相似度反映了節(jié)點(diǎn)所擁有資源的相關(guān)度，節(jié)點(diǎn)的相關(guān)度大，它們進(jìn)行聯(lián)系和互訪的可能性就會(huì)增加，這一點(diǎn)為路由選擇提供了參考，下面給出節(jié)點(diǎn)興趣相似度的定義。

1.2 節(jié)點(diǎn)興趣相似度

對(duì)于網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)所擁有的資源，其特征可以通過(guò)相應(yīng)的關(guān)鍵字來(lái)標(biāo)識(shí)，參照TF*IDF加權(quán)技術(shù)[11］為資源關(guān)鍵字賦予相應(yīng)的權(quán)重。關(guān)鍵字 Ki在資源 Sj中的重要度用權(quán)重 Wij來(lái)表示，Sj=(W1j，W2j，…，Wnj)和 q=(W1q，W2q，…，Wnq)作為資源Sj和搜索請(qǐng)求Q的向量表示，則Sj和Q間的相似度計(jì)算公式如式(1)所示，

圖1 組和域的劃分

在現(xiàn)實(shí)的網(wǎng)絡(luò)環(huán)境中，若節(jié)點(diǎn)Di在某一時(shí)間里多次發(fā)起對(duì)資源Sk的請(qǐng)求，在以后的時(shí)間里節(jié)點(diǎn)Di對(duì)Sk再次發(fā)起請(qǐng)求的可能性很大，擁有資源Sk的節(jié)點(diǎn)Dj對(duì)節(jié)點(diǎn)Di再次響應(yīng)的可能性增大。若節(jié)點(diǎn)Di在單位時(shí)間里從Dj獲取請(qǐng)求響應(yīng)的次數(shù)為Nij，取節(jié)點(diǎn)Di和Dj中資源數(shù)的較小值m，則Di和Dj的資源向量分別表示為 dki=(W1i，W2i，…，Wni)和 dkj=(W1j，W2j，…，Wnj)，在式(1)的基礎(chǔ)上，給出節(jié)點(diǎn) Di和 Dj的興趣相似度h(i，j)如式(2)所示，

由于資源發(fā)現(xiàn)過(guò)程中Nij是動(dòng)態(tài)變化的，節(jié)點(diǎn)所維護(hù)的興趣相似度索引也隨之變化，在域規(guī)模固定的前提下，域中節(jié)點(diǎn)根據(jù)索引表的變化進(jìn)行調(diào)整，動(dòng)態(tài)優(yōu)化系統(tǒng)拓?fù)洌瓜到y(tǒng)中興趣相似度高的節(jié)點(diǎn)聚類在同一域中。

1.3 發(fā)現(xiàn)策略

前面分析的網(wǎng)絡(luò)模型中，域的節(jié)點(diǎn)規(guī)模顯然小于組的節(jié)點(diǎn)規(guī)模，同一域中的節(jié)點(diǎn)可能被劃分在同一組，也可能被劃分到不同的組，資源發(fā)現(xiàn)時(shí)，請(qǐng)求消息首先在本域內(nèi)的同組節(jié)點(diǎn)中傳遞;若同組域內(nèi)發(fā)現(xiàn)失效，則在域內(nèi)其他組的節(jié)點(diǎn)中進(jìn)行消息傳遞;若域內(nèi)組間發(fā)現(xiàn)仍失效，考慮選擇互訪頻繁的友好鄰域進(jìn)行跨域搜索，具體方法如下:

(Ⅰ)搜索發(fā)起者Dq首先訪問(wèn)所在域的超節(jié)點(diǎn)S1，查詢S1的節(jié)點(diǎn)信息索引表，表中記錄了該域的節(jié)點(diǎn)數(shù)目，域內(nèi)普通節(jié)點(diǎn)ID，節(jié)點(diǎn)所在組ID等信息，通過(guò)信息索引表確定S1中Dq所在組的節(jié)點(diǎn)，并在這些節(jié)點(diǎn)中采用k階隨機(jī)走發(fā)現(xiàn)方法搜索請(qǐng)求資源。如果資源發(fā)現(xiàn)成功，進(jìn)行相應(yīng)的一系列動(dòng)態(tài)調(diào)整，如更新Dq與目標(biāo)節(jié)點(diǎn)的興趣相似度值等，為鄰居節(jié)點(diǎn)調(diào)整提供依據(jù)。

(Ⅱ)域內(nèi)同組搜索失效的情況下，查詢S1中的組超節(jié)點(diǎn)索引表，表中存有該域包含的所有組超節(jié)點(diǎn)，這些組超節(jié)點(diǎn)按照與S1的物理距離遞增排列，選擇距S1較近的域內(nèi)組進(jìn)行和域內(nèi)同組搜索相同的資源發(fā)現(xiàn)過(guò)程。

(Ⅲ)如果S1域內(nèi)的所有組均發(fā)現(xiàn)失效，則查詢S1的域友好度索引表(相鄰域表)，相鄰域表中記錄了在S1的組超節(jié)點(diǎn)索引表里所記錄的所有域中與域S1互訪頻繁的域，即與域S1友好度高的域，這些域按訪問(wèn)頻率遞減排列，通過(guò)相鄰域表，轉(zhuǎn)向域友好度最高的域，繼續(xù)根據(jù)具體情況選擇上述兩種方式之一進(jìn)行搜索，直至獲取資源或發(fā)現(xiàn)失敗。

消息路由過(guò)程中，每跳步3次檢測(cè)Dq是否獲取資源，已獲取則停止轉(zhuǎn)發(fā)，避免產(chǎn)生過(guò)多消息冗余;每次發(fā)現(xiàn)目標(biāo)或失敗，都需要對(duì)相應(yīng)節(jié)點(diǎn)所維護(hù)的各索引信息進(jìn)行更新，動(dòng)態(tài)調(diào)整網(wǎng)絡(luò)拓?fù)洹?/p>

2 仿真分析

對(duì)等網(wǎng)絡(luò)資源發(fā)現(xiàn)方法的性能可以從搜索時(shí)間、帶寬利用率、消息冗余等多方面衡量。在前文構(gòu)造的無(wú)結(jié)構(gòu)對(duì)等網(wǎng)的基礎(chǔ)上，著重從搜索時(shí)間和消息冗余這兩方面對(duì)DPIS的查詢性能進(jìn)行評(píng)價(jià)。使用Java語(yǔ)言在模擬環(huán)境下產(chǎn)生不同節(jié)點(diǎn)規(guī)模的網(wǎng)絡(luò)拓?fù)?，設(shè)定節(jié)點(diǎn)平均連接度為10，執(zhí)行周期為200，每個(gè)周期加入100個(gè)新節(jié)點(diǎn)，隨機(jī)選取節(jié)點(diǎn)發(fā)起查詢請(qǐng)求，以平均查詢時(shí)延和消息數(shù)量為主要測(cè)度，為便于觀察，將Flooding和分組后的隨機(jī)漫步G-Random Walk方法作為基準(zhǔn)，與DPIS方法進(jìn)行對(duì)比分析。

圖2是不同網(wǎng)絡(luò)規(guī)模下發(fā)起相同資源請(qǐng)求的平均查詢時(shí)延比較。隨著節(jié)點(diǎn)數(shù)量的增加，盲目搜索的標(biāo)準(zhǔn)泛洪方法Flooding需要將查詢請(qǐng)求向鄰居節(jié)點(diǎn)的鄰居節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，這個(gè)過(guò)程中，延長(zhǎng)了搜索路徑的長(zhǎng)度，產(chǎn)生大量冗余，查詢時(shí)延明顯增加。GRandom僅考慮了節(jié)點(diǎn)的位置因素，目標(biāo)節(jié)點(diǎn)通常并不會(huì)在同組內(nèi)的節(jié)點(diǎn)中出現(xiàn)，即使隨機(jī)漫步選擇了部分鄰居節(jié)點(diǎn)進(jìn)行消息轉(zhuǎn)發(fā)，仍有較大的網(wǎng)絡(luò)消耗，節(jié)點(diǎn)規(guī)模在1 000個(gè)左右時(shí)，平均查詢時(shí)延為0.6～0.7 s。DPIS的局部路由采用k階隨機(jī)走，平均時(shí)延曲線走勢(shì)與G-Random Walk相似，由于根據(jù)興趣相似度將節(jié)點(diǎn)劃歸在組和域內(nèi)，目標(biāo)節(jié)點(diǎn)通常與發(fā)起查詢請(qǐng)求的節(jié)點(diǎn)具有接近的興趣相似度，搜索范圍縮小至同組同域內(nèi)，搜索路徑迅速縮短，路由跳數(shù)減少，隨著節(jié)點(diǎn)規(guī)模的增大，在節(jié)點(diǎn)數(shù)接近1 000個(gè)時(shí)，平均查詢時(shí)延為0.4～0.5 s。

消息轉(zhuǎn)發(fā)數(shù)量從另一方面體現(xiàn)網(wǎng)絡(luò)帶寬利用率，查詢消息被轉(zhuǎn)發(fā)的次數(shù)決定了網(wǎng)絡(luò)中產(chǎn)生的總消息量，相同查詢請(qǐng)求的前提下，總消息量少，說(shuō)明目標(biāo)節(jié)點(diǎn)在較少的路由跳數(shù)內(nèi)被找到，網(wǎng)絡(luò)中產(chǎn)生的消息冗余較少，查詢性能較高。為進(jìn)一步研究驗(yàn)證DPIS的查詢性能，采用不同的網(wǎng)絡(luò)規(guī)模，查看標(biāo)準(zhǔn)泛洪、分組隨機(jī)漫步和DPIS方法中產(chǎn)生的消息轉(zhuǎn)發(fā)數(shù)量，對(duì)比網(wǎng)絡(luò)資源消耗量。

圖2 平均查詢時(shí)延比較

在不同節(jié)點(diǎn)規(guī)模下網(wǎng)絡(luò)中消息轉(zhuǎn)發(fā)數(shù)量的比較結(jié)果如圖3所示。Flooding搜索過(guò)程中節(jié)點(diǎn)向所有鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)消息，節(jié)點(diǎn)數(shù)量增加至接近200時(shí)，網(wǎng)絡(luò)規(guī)模較小，此時(shí)消息數(shù)量增長(zhǎng)較慢，隨著節(jié)點(diǎn)規(guī)模不斷增大，消息數(shù)量急劇增加。G-Random Walk在組內(nèi)選擇部分鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)消息，網(wǎng)絡(luò)規(guī)模對(duì)消息數(shù)量影響比標(biāo)準(zhǔn)泛洪明顯減少，節(jié)點(diǎn)數(shù)量增至近1 000個(gè)時(shí)，消息數(shù)量接近15 000個(gè)。DPIS方法考慮拓?fù)淦ヅ?，同時(shí)將節(jié)點(diǎn)按興趣相似度劃分域，查詢?cè)谟騼?nèi)進(jìn)行，路由跳數(shù)得到控制，減少了冗余消息轉(zhuǎn)發(fā)，在節(jié)點(diǎn)規(guī)模增加的情況下，消息轉(zhuǎn)發(fā)數(shù)量維持在相對(duì)穩(wěn)定的范圍內(nèi)，較G-Random中下降了近50%，與標(biāo)準(zhǔn)泛洪相比，網(wǎng)絡(luò)中產(chǎn)生的消息數(shù)量明顯下降，當(dāng)節(jié)點(diǎn)規(guī)模增至1 000個(gè)，冗余減少達(dá)80%。由此可見(jiàn)，在較大規(guī)模的無(wú)結(jié)構(gòu)對(duì)等網(wǎng)絡(luò)中，DPIS搜索具有控制冗余和減少搜索時(shí)延的優(yōu)越性，提高了搜索效率。

圖3 消息數(shù)量比較

3 結(jié)論

無(wú)結(jié)構(gòu)對(duì)等網(wǎng)絡(luò)中的盲目搜索通過(guò)在網(wǎng)絡(luò)中傳播查詢信息，把信息不斷擴(kuò)散至每個(gè)節(jié)點(diǎn)，這種搜索策略具有高覆蓋率、易于實(shí)現(xiàn)等特點(diǎn)，但它同時(shí)產(chǎn)生大量冗余消息，限制了帶寬利用。針對(duì)無(wú)結(jié)構(gòu)對(duì)等網(wǎng)絡(luò)資源發(fā)現(xiàn)中存在的問(wèn)題，提出了一種基于節(jié)點(diǎn)興趣相似度的資源發(fā)現(xiàn)方法，根據(jù)物理位置對(duì)節(jié)點(diǎn)分組，將興趣相似的節(jié)點(diǎn)聚類形成域，在資源發(fā)現(xiàn)過(guò)程中動(dòng)態(tài)調(diào)整網(wǎng)絡(luò)拓?fù)?，?yōu)化發(fā)現(xiàn)性能。通過(guò)仿真與兩種盲目搜索方法的性能進(jìn)行了比較，并分析了仿真結(jié)果，但無(wú)結(jié)構(gòu)覆蓋網(wǎng)絡(luò)搜索中資源的準(zhǔn)確定位，提高查全率等問(wèn)題仍需在以后工作中進(jìn)一步研究。

[1]陳貴海，李振華.對(duì)等網(wǎng)絡(luò):結(jié)構(gòu)、應(yīng)用與設(shè)計(jì)[M］.北京:清華大學(xué)出版社，2007.

[2]李運(yùn)娣，馮勇.基于DHT的P2P搜索定位技術(shù)研究[J］.計(jì)算機(jī)應(yīng)用研究，2006，23(10):226-228

[3]Ripeanu M.Peer-to-Peer Architecture Case Study:Gnutella Network[C］//Proceedings of 1st International Conference on Peer-to-Peer Computing.2001:99-100.

[4]徐浩，歐陽(yáng)松.無(wú)結(jié)構(gòu)P2P系統(tǒng)的重疊網(wǎng)拓?fù)鋬?yōu)化[J］.計(jì)算機(jī)工程與應(yīng)用，2010，46(22):144-146.

[5]吳開(kāi)貴，曾家國(guó)，吳長(zhǎng)澤，等.基于預(yù)算機(jī)制的非結(jié)構(gòu)化P2P網(wǎng)絡(luò)搜索算法[J］.計(jì)算機(jī)應(yīng)用，2010，30(5):1166-1170.

[6]朱桂明，郭得科，金士堯.基于副本復(fù)制和Bloom Filter的P2P概率路由算法[J］.軟件學(xué)報(bào)，2011，22(4):773-781.

[7]張茉莉，張延園，唐焱，等.利用P2P網(wǎng)絡(luò)的拓樸特征提高其路由性能[J］.河南科技大學(xué)學(xué)報(bào):自然科學(xué)版，2006，27(5):42-44.

[8]Song J，Lei G，Zhang X D.Light Flooding:Minizing Redundant Message and Maximizing the Scope of Peer-to-Peer Search[J］.IEEE Transactions on Parallel and Distributed Systems，2008，19(5):601-614.

[9]劉智勇，鄭滔，伍偉績(jī).基于隨機(jī)漫步的信任路徑搜索算法[J］.計(jì)算機(jī)工程，2009，35(18):156-158.

[10]Lv Q，Cao P，Cohen E，et al.Search and Replication in Unstructured Peer-to-Peer Networks[C］//Proceedings of the 16th ACM International Conference on Supercomputing.2002.

[11]陳旭，陳德華，樂(lè)嘉錦.基于語(yǔ)義相關(guān)度排序的政務(wù)信息資源檢索算法[J］.計(jì)算機(jī)工程與應(yīng)用，2011，47(25):121-125.