基于標(biāo)簽匹配的P2P信息檢索算法

摘 要：對(duì)于非結(jié)構(gòu)化P2P網(wǎng)絡(luò)而言，資源的高效搜索成為廣泛研究的關(guān)鍵技術(shù)。本文提出了一種基于標(biāo)簽匹配的信息檢索算法，將請(qǐng)求表示為多關(guān)鍵字向量，對(duì)請(qǐng)求和資源信息的標(biāo)簽進(jìn)行匹配，并對(duì)搜索結(jié)果進(jìn)行評(píng)分排序，選取符合要求的信息。本算法充分考慮了多種因素對(duì)搜索效率的影響，大大提高了搜索結(jié)果的精確性。

關(guān)鍵詞：非結(jié)構(gòu)化P2P網(wǎng)絡(luò)；標(biāo)簽匹配；權(quán)重；評(píng)分排序

中圖分類號(hào)：TP393.02

1 研究現(xiàn)狀

P2P（peer-to-peer，點(diǎn)對(duì)點(diǎn)）網(wǎng)絡(luò)是當(dāng)前十分流行的網(wǎng)絡(luò)技術(shù)，它的出現(xiàn)對(duì)分布式計(jì)算以及整個(gè)因特網(wǎng)來說，都是一場(chǎng)巨大的革新，從P2P網(wǎng)絡(luò)誕生之日起，關(guān)于它的研究和應(yīng)用就成為熱點(diǎn)。它最大的特點(diǎn)是網(wǎng)絡(luò)結(jié)構(gòu)的疏松性，即節(jié)點(diǎn)的加入和離開都是十分自由的，尤其是非結(jié)構(gòu)化P2P網(wǎng)絡(luò)，所有的節(jié)點(diǎn)完全是動(dòng)態(tài)不受約束的。因此，對(duì)P2P網(wǎng)絡(luò)中節(jié)點(diǎn)的精確定位以及資源的高效搜索成為P2P網(wǎng)絡(luò)的關(guān)鍵技術(shù)。

現(xiàn)有P2P的組織結(jié)構(gòu)按搜索機(jī)制主要分為三類：

（1）集中索引式的，如Napster。其中心服務(wù)器會(huì)成為整個(gè)網(wǎng)絡(luò)的瓶頸。

（2）請(qǐng)求泛洪式的，屬于分散式、非結(jié)構(gòu)化的模型，如Gnutella。泛洪式搜索算法會(huì)產(chǎn)生大量的冗余查詢包，成為網(wǎng)絡(luò)的瓶頸而限制網(wǎng)絡(luò)的性能。

（3）分布式哈希表（DHT，Distributed Hash Table），屬于分散式，結(jié)構(gòu)化的模型，如CAN、Chord、Pastry等。檢索時(shí)必須知道目標(biāo)對(duì)象的唯一標(biāo)識(shí)，不支持基于多標(biāo)簽的信息檢索。

對(duì)于非結(jié)構(gòu)化P2P網(wǎng)絡(luò)，常用的泛洪式的搜索算法編碼簡(jiǎn)單，易于實(shí)現(xiàn)。但查詢效率低下，而且會(huì)產(chǎn)生大量的冗余查詢包，造成網(wǎng)絡(luò)擁塞而限制網(wǎng)絡(luò)的性能。一些新的算法對(duì)其進(jìn)行了改進(jìn)，減少了資源搜索過程中的盲目性，但仍存在一些缺陷，如沒有考慮到目標(biāo)節(jié)點(diǎn)資源的匹配度等關(guān)鍵因素，導(dǎo)致搜索過程過于繁瑣。

針對(duì)以上問題，本文提出了一種基于標(biāo)簽匹配的搜索算法。該算法充分考慮節(jié)點(diǎn)的動(dòng)態(tài)性，引入超級(jí)節(jié)點(diǎn)進(jìn)行動(dòng)態(tài)管理，節(jié)點(diǎn)信息動(dòng)態(tài)匹配，保證了資源的有效性。

2 算法實(shí)現(xiàn)策略

在每個(gè)節(jié)點(diǎn)加入P2P網(wǎng)絡(luò)時(shí)，都會(huì)被分配一個(gè)ID作為唯一標(biāo)識(shí)。在一定范圍的物理區(qū)域內(nèi)，會(huì)根據(jù)節(jié)點(diǎn)的吞吐能力以及穩(wěn)定性推舉出一個(gè)超級(jí)節(jié)點(diǎn)，超級(jí)節(jié)點(diǎn)中除了存儲(chǔ)本地的相關(guān)資源外，還會(huì)創(chuàng)建一個(gè)查詢表，存儲(chǔ)所管轄區(qū)域內(nèi)各節(jié)點(diǎn)所包含資源所對(duì)應(yīng)的ID及多重標(biāo)簽。每個(gè)區(qū)域中還需要選舉出一個(gè)備用超級(jí)節(jié)點(diǎn)，當(dāng)超級(jí)節(jié)點(diǎn)突然退出或崩潰時(shí)，可以充當(dāng)超級(jí)節(jié)點(diǎn)。

當(dāng)一個(gè)節(jié)點(diǎn)需要下載某類型的資源時(shí)，將請(qǐng)求表示為多關(guān)鍵字向量并發(fā)送到超級(jí)節(jié)點(diǎn)，超級(jí)節(jié)點(diǎn)會(huì)將其與已存的各節(jié)點(diǎn)的標(biāo)簽進(jìn)行比較，選出符合條件的資源進(jìn)行評(píng)分排序，并返回給申請(qǐng)資源的節(jié)點(diǎn)，節(jié)點(diǎn)選出想要連接的資源，搜索其節(jié)點(diǎn)ID，找到相應(yīng)的目的節(jié)點(diǎn)，建立連接，實(shí)現(xiàn)資源的下載。若在同一個(gè)超級(jí)節(jié)點(diǎn)下無(wú)法找到標(biāo)簽一致的節(jié)點(diǎn)，則超級(jí)節(jié)點(diǎn)會(huì)向鄰近的超級(jí)節(jié)點(diǎn)發(fā)送搜索信息進(jìn)行搜索，一旦匹配，就會(huì)建立連接并進(jìn)行資源傳輸。

在網(wǎng)絡(luò)創(chuàng)建初期，由于節(jié)點(diǎn)之間并不熟悉，資源的來源無(wú)法預(yù)測(cè)，利用超級(jí)節(jié)點(diǎn)進(jìn)行輔助搜索。隨著網(wǎng)絡(luò)的成熟，節(jié)點(diǎn)間的交流增多，某些節(jié)點(diǎn)之間形成固定的信息互發(fā)，給節(jié)點(diǎn)間互發(fā)信息次數(shù)設(shè)定一個(gè)閾值，當(dāng)達(dá)到這個(gè)閾值后，兩個(gè)節(jié)點(diǎn)互相將對(duì)方加入朋友列表，直接進(jìn)行信息交流。這樣節(jié)點(diǎn)就可以不必通過超級(jí)節(jié)點(diǎn)的中轉(zhuǎn)而直接進(jìn)行信息交流，減少因?yàn)槌?jí)節(jié)點(diǎn)的轉(zhuǎn)發(fā)而造成的損耗。

為了方便資源搜索，網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)都需要維護(hù)三張數(shù)據(jù)表：

（1）本地資源表，用來維護(hù)本地的資源信息，方便其它節(jié)點(diǎn)進(jìn)行資源請(qǐng)求；

（2）歷史記錄表，記錄一段時(shí)間內(nèi)該節(jié)點(diǎn)查詢過的資源信息，該表中包括的資源信息主要分為查找成功的資源和查找不成功的資源兩種。對(duì)于查找成功的資源則保存獲取該資源的地址，而對(duì)于查找不成功的資源則需要保存該資源被請(qǐng)求過的次數(shù)，并且為每一條記錄保存相應(yīng)的更新時(shí)間戳，當(dāng)表內(nèi)空間不足時(shí)，按照時(shí)間戳將存放時(shí)間最長(zhǎng)的數(shù)據(jù)置換出去。該表主要用于流行資源的快捷查詢；

（3）朋友節(jié)點(diǎn)信息表，存放朋友節(jié)點(diǎn)信息。

2.1 超級(jí)節(jié)點(diǎn)的選擇算法

P2P網(wǎng)絡(luò)中的超級(jí)節(jié)點(diǎn)主要實(shí)現(xiàn)以下幾點(diǎn)功能：

（1）處理來自其管轄區(qū)域子節(jié)點(diǎn)和自身的查詢信息；

（2）轉(zhuǎn)發(fā)并處理來自其他超級(jí)節(jié)點(diǎn)的查詢信息。

因此，如何選擇那些在線時(shí)間長(zhǎng)并且吞吐能力強(qiáng)的節(jié)點(diǎn)作為超級(jí)節(jié)點(diǎn)是問題的關(guān)鍵。

本文定義了兩個(gè)變量來衡量一個(gè)節(jié)點(diǎn)是否適合成為超級(jí)節(jié)點(diǎn)：Stability和Capacity。Stability代表了節(jié)點(diǎn)的穩(wěn)定性，Capacity代表了節(jié)點(diǎn)的吞吐能力。綜合以上兩點(diǎn)，算法周期性地對(duì)節(jié)點(diǎn)i進(jìn)行評(píng)分：

Score[i]=m×Stability[i]+n×Capacity[i] （m+n=1）

關(guān)于選舉的時(shí)機(jī)：雖然時(shí)間越短越準(zhǔn)確，但是會(huì)導(dǎo)致通信量越大。因此，采用事件驅(qū)動(dòng)的策略，即節(jié)點(diǎn)的加入、超級(jí)節(jié)點(diǎn)的離開等觸發(fā)選舉。

2.2 評(píng)分排序算法

在大數(shù)據(jù)的網(wǎng)絡(luò)背景下，節(jié)點(diǎn)進(jìn)行資源搜索時(shí)，利用標(biāo)簽匹配搜索到的資源很多，需要我們將搜索到的資源進(jìn)行評(píng)分，按評(píng)分高低排序后將結(jié)果返回到用戶節(jié)點(diǎn)，有利于用戶更加快捷的選擇合適的資源。

篩選資源時(shí)應(yīng)綜合考慮多個(gè)因素：資源標(biāo)簽與關(guān)鍵字向量的匹配度；目標(biāo)節(jié)點(diǎn)資源被其他節(jié)點(diǎn)引用的次數(shù)；路由跳數(shù)，即物理距離；資源更新時(shí)間，因?yàn)橘Y源越新，下載用戶越聚集，速度越快。各分量占據(jù)不同的權(quán)重。

下面是資源評(píng)分的表達(dá)式：

Score=aM+bQ+cD+dT （a+b+c+d=1）

其中，M表示匹配度，Q表示被引用的次數(shù)，D表示物理距離，T表示更新的時(shí)間，a、b、c、d分別表示各項(xiàng)指標(biāo)的權(quán)重。

2.3 降低負(fù)載

由于并不知道P2P網(wǎng)絡(luò)中數(shù)據(jù)的總量，導(dǎo)致查詢范圍過大，網(wǎng)絡(luò)的帶寬、負(fù)載等因素都會(huì)影響查詢響應(yīng)時(shí)間。設(shè)定一個(gè)查詢超時(shí)時(shí)間Tl（或是對(duì)查詢結(jié)果的總數(shù)設(shè)定一個(gè)閾值，達(dá)到閾值后停止搜索），當(dāng)查詢時(shí)間超過Tl時(shí)，停止查詢，并將查詢結(jié)果返回給用戶。

為了更好的完善下載環(huán)境，每次資源下載完成后，節(jié)點(diǎn)對(duì)所下載資源的下載速率、視頻質(zhì)量等進(jìn)行評(píng)分，并在后續(xù)其他節(jié)點(diǎn)搜索時(shí)，顯示在搜索結(jié)果中。

3 結(jié)束語(yǔ)

本文提出的基于標(biāo)簽匹配的搜索算法，對(duì)現(xiàn)有的有關(guān)非結(jié)構(gòu)化P2P網(wǎng)絡(luò)的搜索算法進(jìn)行了改進(jìn)，引入主題標(biāo)簽并綜合考慮資源篩選時(shí)的多個(gè)因素，有效提高了資源搜索的匹配度，減少了網(wǎng)絡(luò)中的通信量和搜索的平均消息數(shù)目，縮短了平均路徑距離，提高了查詢效率。

參考文獻(xiàn)：

[1]曾宇斌，劉貴全.P2P網(wǎng)絡(luò)中基于多關(guān)鍵字的信息檢索研究[J].計(jì)算機(jī)應(yīng)用與軟件，2007（08）：119-121.

[2]朱凡微，吳明暉，金蒼宏.基于關(guān)鍵字的數(shù)據(jù)庫(kù)搜索研究綜述[J].計(jì)算機(jī)應(yīng)用研究，2008（11）：3238-3242.

[3]相有桓，熊焰，苗付友.移動(dòng)P2P網(wǎng)絡(luò)中超級(jí)節(jié)點(diǎn)的選擇[J].計(jì)算機(jī)工程，2010（10）：103-107.

[4]郭良敏，楊壽保，郭磊濤.P2P網(wǎng)絡(luò)中基于區(qū)域劃分的超級(jí)節(jié)點(diǎn)選取機(jī)制[J].小型微型計(jì)算機(jī)系統(tǒng)，2008（02）：208-212.

作者簡(jiǎn)介：莊芳芳（1988-），女，山東煙臺(tái)人，碩士研究生，研究方向：計(jì)算機(jī)網(wǎng)絡(luò)。

作者單位：遼寧大學(xué)，沈陽(yáng) 110036