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

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

中圖分類號：TP393.02

1 研究現(xiàn)狀

P2P（peer-to-peer，點(diǎn)對點(diǎn)）網(wǎng)絡(luò)是當(dāng)前十分流行的網(wǎng)絡(luò)技術(shù)，它的出現(xiàn)對分布式計算以及整個因特網(wǎ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)完全是動態(tài)不受約束的。因此，對P2P網(wǎng)絡(luò)中節(jié)點(diǎn)的精確定位以及資源的高效搜索成為P2P網(wǎng)絡(luò)的關(guān)鍵技術(shù)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 評分排序算法

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

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

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

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

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

2.3 降低負(fù)載

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

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

3 結(jié)束語

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

參考文獻(xiàn)：

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

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

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

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

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

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